loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008)
Waikoloa, Big Island, Hawaii
January 07-January 10
ISBN: 0-7695-3075-3
In this paper we consider finding a minimum-sum dipolar spanning tree in R3, and present an algorithm that takes O(n2 log2 n) time using O(n2) space, thus almost match- ing the best known results for the planar case. To achieve this, we prove an interesting result related to the complex- ity of the common intersection of n balls in R3, of possi- ble 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 net- work to the closer of the two hubs, and could lead to reduc- tion in power consumption for devices like PDAs, sensors, cell phones and laptops.
Citation:
Steven Bitner, Ovidiu Daescu, "Finding a Minimum-Sum Dipolar Spanning Tree in R3," hicss, pp.470, Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.