The Minimum Manhattan Network Problem: Approximations and Exact Solutions | BibSonomy

The Minimum Manhattan Network Problem: Approximations and Exact Solutions
, , , und .
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
Diese Publikation wurde noch nicht bewertet.

Durchschnittliche Benutzerbewertung0,0 von 5.0 auf Grundlage von 0 Rezensionen
    Bitte melden Sie sich an um selbst Rezensionen oder Kommentare zu erstellen.