The Minimum Manhattan Network Problem:
Approximations and Exact Solutions

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.

- URL
- http://dx.doi.org/10.1016/j.comgeo.2005.09.004
- search on

approximation_algorithmdblpjabref:nokeywordassignedminimum_manhattan_networksmixed-integer_programmingmyownspanner

This publication has not been reviewed yet.

rating distribution

average user rating0.0 out of 5.0 based on 0 reviews