Finding a Minimum-Sum Dipolar Spanning Tree in R3

Published in HICSS 2008, 2008

Recommended citation:

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, yS that minimize the sum |xy|+max{rx, ry}, where rx and ry are the radii of two disks with centers at x and y, respetively, that together cover all points in S. We present an O(n2log2n) time algorithm that uses O(n2) space, improving upon the known three dimensional result of O(n2.5+ε) time and O(n2) space.

Download paper here