Minimum Sum Dipolar Spanning Tree in R^3

Details Minimum Sum Dipolar Spanning Tree in R^3 Minimum Sum Dipolar Spanning Tree in R^3

2010-07-07

arxiv.org/abs/1007.1222v1

Computer Science

Computational Geometry

11 pages, 4 figures, submitted to Computational Geometry: Theory and Applications

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Minimum Sum Dipolar Spanning Tree in R^3 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Sum Dipolar Spanning Tree in R^3, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Sum Dipolar Spanning Tree in R^3 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-346406