Facility Location and the Geometric Minimum-Diameter
Spanning Tree
Computational Geometry: Theory and Applications, 27 (1):
87--106 (2004)DOI: 10.1016/j.comgeo.2003.07.007
Abstract
Let $P$ be a set of $n$ points in the plane. The
geometric minimum-diameter spanning tree (MDST) of
$P$ is a tree that spans $P$ and minimizes the
Euclidian length of the longest path. It is known
that there is always a mono- or a dipolar MDST,
i.e.\ a MDST with one or two nodes of degree greater
1, respectively. The more difficult dipolar case can
so far only be solved in slightly subcubic
time. This paper has two aims. First, we
present a solution to a new data structure for
facility location, the minimum-sum dipolar spanning
tree (MSST), that mediates between the
minimum-diameter dipolar spanning tree and the
discrete two-center problem (2CP) in the following
sense: find two centers $p$ and $q$ in $P$ that
minimize the sum of their distance plus the distance
of any other point (client) to the closer
center. This is of interest if the two centers do
not only serve their customers (as in the case of
the 2CP), but frequently have to exchange goods or
personnel between themselves. We give an $O(n^2 łog
n)$-time algorithm for this problem. A slight
modification of our algorithm yields a factor-4/3
approximation of the MDST. Second, we give two
fast approximation schemes for the MDST, i.e.\
factor-($1+\varepsilon$) approximation
algorithms. One uses a grid and takes
$O^*(E^6-1/3+n)$ time, where $E=1/\varepsilon$ and
the $O^*$-notation hides terms of type
$O(łog^O(1) E)$. The other uses the
well-separated pair decomposition and takes $O(n E^3
+ E n n)$ time. A combination of the two
approaches runs in $O^*(E^5 + n)$ time. Both schemes
can also be applied to MSST and 2CP.
