Minimum-sum dipolar spanning tree in R^3

DOI10.1016/J.COMGEO.2010.09.011MaRDI QIDQ452446zbMATH OpenOpenAlexFDO

Authors Steven Bitner, Ovidiu Daescu

Publication date 21 September 2012

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.1222

zbMATH Keywords

algorithmcomputational geometrycommunication networksdipolar spanning treeintersection of balls

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Analytic circuit theory (94C05)

Abstract: In this paper we consider finding a geometric minimum-sum dipolar spanning tree in R^3, and present an algorithm that takes O(n^2 log^2 n) time using O(n^2) space, thus almost matching the best known results for the planar case. Our solution uses an interesting result related to the complexity of the common intersection of n balls in R^3, of possible different radii, that are all tangent to a given point p. The problem has applications in communication networks, when the goal is to minimize the distance between two hubs or servers as well as the distance from any node in the network to the closer of the two hubs. The approach used in this paper also provides a solution to the discrete 2-center problem in R^3 within the same time and space bounds.

Recommendations

• scientific article; zbMATH DE number 1947054
• Minimum Spanning Trees in k-Dimensional Space
• Facility location and the geometric minimum-diameter spanning tree.
• Computing a (1+)-approximate geometric minimum-diameter spanning tree
• Minimum spanning trees in d dimensions

Cites work

• scientific article; zbMATH DE number 3887061 (Why is no real title available?)
• scientific article; zbMATH DE number 3122839 (Why is no real title available?)
• scientific article; zbMATH DE number 3855110 (Why is no real title available?)
• scientific article; zbMATH DE number 1947054 (Why is no real title available?)
• scientific article; zbMATH DE number 6472586 (Why is no real title available?)
• A near-linear algorithm for the planar 2-center problem
• An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra
• Computational Geometry in C
• Efficiently approximating polygonal paths in three and higher dimensions
• Facility location and the geometric minimum-diameter spanning tree.
• Finding Minimum Spanning Trees
• Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• Minimum Diameter Spanning Trees and Related Problems
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Semi-Online Maintenance of Geometric Optima and Measures
• The discrete 2-center problem

Cited in

(1)

• scientific article; zbMATH DE number 7478573 (Why is no real title available?)

This page was built for publication: Minimum-sum dipolar spanning tree in \(\mathbb R^3\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q452446)