Approximating Minimum Manhattan Networks in Higher Dimensions

Aparna Das; Emden R. Gansner; Michael Kaufmann; Stephen Kobourov; Joachim Spoerhase; Alexander Wolff

doi:10.1007/s00453-013-9778-z

Approximating Minimum Manhattan Networks in Higher Dimensions

Aparna Das, Emden R. Gansner, Michael Kaufmann, Stephen Kobourov, Joachim Spoerhase, Alexander Wolff

Computer Science

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in (Formula presented.), find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair’s Manhattan (that is, L₁-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless (Formula presented.)). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension d and any ε>0, an O(n^ε)-approximation algorithm. For 3D, we also give a 4(k−1)-approximation algorithm for the case that the terminals are contained in the union of k≥2 parallel planes.

Original language	English (US)
Pages (from-to)	36-52
Number of pages	17
Journal	Algorithmica
Volume	71
Issue number	1
DOIs	https://doi.org/10.1007/s00453-013-9778-z
State	Published - Jan 2013

Keywords

Approximation algorithms
Computational geometry
Minimum Manhattan network

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s00453-013-9778-z

Cite this

@article{44c9d935d44c4d10b15414a9bb9530ef,

title = "Approximating Minimum Manhattan Networks in Higher Dimensions",

abstract = "We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in (Formula presented.), find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair{\textquoteright}s Manhattan (that is, L1-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless (Formula presented.)). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension d and any ε>0, an O(nε)-approximation algorithm. For 3D, we also give a 4(k−1)-approximation algorithm for the case that the terminals are contained in the union of k≥2 parallel planes.",

keywords = "Approximation algorithms, Computational geometry, Minimum Manhattan network",

author = "Aparna Das and Gansner, {Emden R.} and Michael Kaufmann and Stephen Kobourov and Joachim Spoerhase and Alexander Wolff",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Science+Business Media New York.",

year = "2013",

month = jan,

doi = "10.1007/s00453-013-9778-z",

language = "English (US)",

volume = "71",

pages = "36--52",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Approximating Minimum Manhattan Networks in Higher Dimensions

AU - Das, Aparna

AU - Gansner, Emden R.

AU - Kaufmann, Michael

AU - Kobourov, Stephen

AU - Spoerhase, Joachim

AU - Wolff, Alexander

PY - 2013/1

Y1 - 2013/1

N2 - We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in (Formula presented.), find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair’s Manhattan (that is, L1-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless (Formula presented.)). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension d and any ε>0, an O(nε)-approximation algorithm. For 3D, we also give a 4(k−1)-approximation algorithm for the case that the terminals are contained in the union of k≥2 parallel planes.

AB - We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in (Formula presented.), find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair’s Manhattan (that is, L1-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless (Formula presented.)). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension d and any ε>0, an O(nε)-approximation algorithm. For 3D, we also give a 4(k−1)-approximation algorithm for the case that the terminals are contained in the union of k≥2 parallel planes.

KW - Approximation algorithms

KW - Computational geometry

KW - Minimum Manhattan network

UR - http://www.scopus.com/inward/record.url?scp=84922000454&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84922000454&partnerID=8YFLogxK

U2 - 10.1007/s00453-013-9778-z

DO - 10.1007/s00453-013-9778-z

M3 - Article

AN - SCOPUS:84922000454

SN - 0178-4617

VL - 71

SP - 36

EP - 52

JO - Algorithmica

JF - Algorithmica

IS - 1

ER -

Approximating Minimum Manhattan Networks in Higher Dimensions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this