Approximating the Geometric Minimum-Diameter Spanning Tree
Source file as Portable Document Format Postscript Document

Preprint series: Preprint-Reihe Mathematik, 4/2002

MSC 2000

05C85 Graph algorithms

68W25 Approximation algorithms

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 whose longest path consists of two or three edges, respectively. The more difficult dipolar case can so far only be solved in $O(n^3)$ time.

This paper has two aims. First, we present a solution to a new facility location problem, denoted 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 show that this problem can be solved in $O(n^2 \log n)$ time and that a variant of our solution yields a factor-1.2 approximation of the MDST.

Second, we give two fast approximation schemes for the MDST, i.e.\ factor-($1 + \epsilon$) approximation algorithms. Let $E = 1/\epsilon$. One uses a grid and takes $O(E^6 + n)$ time. The other uses a well-separated pair decomposition and takes $O(n E^3 + E n \log n)$ time. A combination of the two approaches runs in $O(E^5 + n)$ time, i.e. a linear-time approximation scheme of order 5. Both can also be applied to MSST and 2CP.

Keywords: Computational geometry, algorithmic graph theory, geometric networks, approximation algorithms, linear-time approximation schemes.