# Finding a Minimum-Sum Dipolar Spanning Tree in R^{3}

Published in *HICSS 2008*, 2008

Recommended citation: __https://ieeexplore.ieee.org/document/4439175__

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*}, where

_{y}*r*and

_{x}*r*are the radii of two disks with centers at

_{y}*x*and

*y*, respetively, that together cover all points in S. We present an

*O(n*time algorithm that uses

^{2}log_{2}n)*O(n*space, improving upon the known three dimensional result of

^{2})*O(n*time and

^{2.5+ε})*O(n*space.

^{2})