Finding a Minimum-Sum Dipolar Spanning Tree in R³

We disuss the problem of finding the minimum-sum dipolar spanning tree (MSST) in three dimensions. The MSST problem is a minimization problem wherein given a set S of n points the goal is to find two points x, y ∈ S that minimize the sum |xy|+max{r_x, r_y}, where r_x and r_y are the radii of two disks with centers at x and y, respetively, that together cover all points in S. We present an O(n²log₂n) time algorithm that uses O(n²) space, improving upon the known three dimensional result of O(n^2.5+ε) time and O(n²) space.

Download paper here