Minimum-sum dipolar spanning tree in R^3

DOI10.1016/J.COMGEO.2010.09.011zbMATH Open1251.65017arXiv1007.1222OpenAlexW1570657273MaRDI QIDQ452446FDOQ452446

Authors: Steven Bitner, Ovidiu Daescu 

Publication date: 21 September 2012

Published in: Computational Geometry (Search for Journal in Brave)

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.

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

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+\varepsilon)\)-approximate geometric minimum-diameter spanning tree
• Minimum spanning trees in \(d\) dimensions

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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)