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.
%0 Journal Article
%1 bwws-mmnpa-06
%A Benkert, Marc
%A Wolff, Alexander
%A Widmann, Florian
%A Shirabe, Takeshi
%D 2006
%J #CGTA#
%K
%N 3
%P 188--208
%R 10.1016/j.comgeo.2005.09.004
%T The Minimum Manhattan Network Problem: Approximations and Exact Solutions
%U http://dx.doi.org/10.1016/j.comgeo.2005.09.004
%V 35
%X 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.
@article{bwws-mmnpa-06,
abstract = {Given a set of points in the plane and a constant $t\ge 1$, a Euclidean $t$-\emph{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 \emph{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 \log 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.},
added-at = {2010-04-13T09:41:33.000+0200},
author = {Benkert, Marc and Wolff, Alexander and Widmann, Florian and Shirabe, Takeshi},
biburl = {https://www.bibsonomy.org/bibtex/289a59aed6429ee107d14802dad9e96c8/fink},
doi = {10.1016/j.comgeo.2005.09.004},
interhash = {f4c49f0bf7caef07f1bfb0a6091c6d4a},
intrahash = {89a59aed6429ee107d14802dad9e96c8},
journal = {#CGTA#},
keywords = {},
number = 3,
pages = {188--208},
pdf = {#AWPUBURL#bwws-mmnpa-06.pdf},
succeeds = {bww-mmnpf-05},
timestamp = {2010-04-13T09:41:33.000+0200},
title = {The Minimum {Manhattan} Network Problem: Approximations and Exact Solutions},
url = {http://dx.doi.org/10.1016/j.comgeo.2005.09.004},
volume = 35,
year = 2006
}