Minimum-sum Dipolar Spanning Tree in R³

In this paper we consider finding a geometric minimum-sum dipolar spanning tree in R³, and present an algorithm that takes O(n²log₂²n) time using O(n²) 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³, 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.

Download paper here