The Minimum Manhattan Network Problem: Approximations and Exact Solutions
#CGTA#, 35 (3):
188--208 (2006)DOI: 10.1016/j.comgeo.2005.09.004
Abstract
Given a set of points in the plane and a constant $t1$, a Euclidean $t$-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most~$t$. Such networks have applications in transportation or communication network design and have been studied extensively. In this paper we study 1-spanners under the Manhattan (or $L_1$-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an $x$- and $y$-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e.\ Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set $P$ of $n$ points, our algorithm computes in $O(n n)$ time and linear space a Manhattan network for $P$ whose length is at most 3 times the length of an MMN of $P$. We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets.
Links and resources
Tags
community
@fink's tags highlighted