Change search
ReferencesLink to record
Permanent link

Direct link
The Minimum Manhattan Network Problem: Approximations and Exact Solutions
Institute for Geoinformation, Technical University of Vienna.ORCID iD: 0000-0001-5572-7395
2006 (English)In: Computational geometry, ISSN 0925-7721, E-ISSN 1879-081X, Vol. 35, no 3, 188-208 p.Article in journal (Refereed) Published
Abstract [en]

Given a set of points in the plane and a constant t⩾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.

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 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(nlogn) 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.

Place, publisher, year, edition, pages
Elsevier, 2006. Vol. 35, no 3, 188-208 p.
Keyword [en]
Spanners, Minimum Manhattan networks, Approximation algorithm, Mixed-integer programming
National Category
Computer Science
URN: urn:nbn:se:kth:diva-66463DOI: 10.1016/j.comgeo.2005.09.004ISI: 000240795500004ScopusID: 2-s2.0-84867954426OAI: diva2:484115

QC 20120126

Available from: 2012-01-26 Created: 2012-01-26 Last updated: 2016-05-23Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Shirabe, Takeshi
In the same journal
Computational geometry
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 34 hits
ReferencesLink to record
Permanent link

Direct link