The Minimum Manhattan Network Problem: Approximations and Exact Solutions
, , , and .
Computational Geometry: Theory and Applications 35 (3): 188--208 (2006)

Given a set of points in the plane and a constant $t\ge 1$, 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. \par 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 łog n)$ time and linear space a Manhattan network for $P$ whose length is at most 3 times the length of an MMN of $P$. \par 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.
  • @awolff
  • @dblp
  • @fink
This publication has not been reviewed yet.

rating distribution
average user rating0.0 out of 5.0 based on 0 reviews
    Please log in to take part in the discussion (add own reviews or comments).