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 Computational Geometry: Theory and Applications
%K approximation_algorithm minimum_Manhattan_networks mixed-integer_programming myown spanner
%N 3
%P 188--208
%R 10.1016/j.comgeo.2005.09.004
%T The Minimum Manhattan Network Problem:
Approximations and Exact Solutions
%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 = {2024-07-14T10:03:47.000+0200},
author = {Benkert, Marc and Wolff, Alexander and Widmann, Florian and Shirabe, Takeshi},
biburl = {https://www.bibsonomy.org/bibtex/2fb1fd2433d30d802092ddf6649aeb1c6/awolff},
doi = {10.1016/j.comgeo.2005.09.004},
interhash = {f4c49f0bf7caef07f1bfb0a6091c6d4a},
intrahash = {fb1fd2433d30d802092ddf6649aeb1c6},
journal = {Computational Geometry: Theory and Applications},
keywords = {approximation_algorithm minimum_Manhattan_networks mixed-integer_programming myown spanner},
number = 3,
pages = {188--208},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/bwws-mmnpa-06.pdf},
succeeds = {bww-mmnpf-05},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {The Minimum {Manhattan} Network Problem:
Approximations and Exact Solutions},
volume = 35,
year = 2006
}