KIT | KIT-Bibliothek | Impressum | Datenschutz

The Minimum Manhattan Network Problem: A Fast Factor-3 Approximation

Benkert, Marc; Widmann, Florian; Wolff, Alexander


Given a set of nodes in the plane and a constant t > 1, a Euclidean t-spanner is a network in which, for any pair of nodes, the ratio of the network distance and the Euclidean distance of the two nodes 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 L1-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of nodes can be seen as a set of axis-parallel line segments whose union contains a Manhattan path for each pair of nodes. 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 a factor-3 approximation algorithm for this problem. Given a set P of n nodes, 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. We have implemented our algorithm and have done a thorough experimental analysis.

Open Access Logo

Volltext §
DOI: 10.5445/IR/1000003164
Zugehörige Institution(en) am KIT Institut für Logik, Komplexität und Deduktionssysteme (ILKD)
Publikationstyp Forschungsbericht
Jahr 2004
Sprache Deutsch
Identifikator ISSN: 1432-7864
KITopen-ID: 1000003164
Verlag Universität Karlsruhe, Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2004,16
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page