We study the minimum Manhattan network problem,
which is defined as follows. Given a set of points
called terminals in~$R^d$, 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_1$-) distance. The
problem is NP-hard in 2D and there is no PTAS for 3D
(unless $P = NP$). Approximation
algorithms are known for 2D, but not for 3D. We
present, for any fixed dimension~$d$ and any
$\epsilon>0$, an $O(n^\epsilon)$-approxi\-ma\-tion
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 \ge
2$ parallel planes.
%0 Journal Article
%1 dgkksw-ammnh-Algorithmica15
%A Das, Aparna
%A Gansner, Emden R.
%A Kaufmann, Michael
%A Kobourov, Stephen
%A Spoerhase, Joachim
%A Wolff, Alexander
%D 2015
%J Algorithmica
%K approximation_algorithms computational_geometry minimum_Manhattan_networks myown
%N 1
%P 36--52
%R 10.1007/s00453-013-9778-z
%T Approximating Minimum Manhattan Networks in Higher
Dimensions
%V 71
%X We study the minimum Manhattan network problem,
which is defined as follows. Given a set of points
called terminals in~$R^d$, 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_1$-) distance. The
problem is NP-hard in 2D and there is no PTAS for 3D
(unless $P = NP$). Approximation
algorithms are known for 2D, but not for 3D. We
present, for any fixed dimension~$d$ and any
$\epsilon>0$, an $O(n^\epsilon)$-approxi\-ma\-tion
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 \ge
2$ parallel planes.
@article{dgkksw-ammnh-Algorithmica15,
abstract = {We study the minimum Manhattan network problem,
which is defined as follows. Given a set of points
called \emph{terminals} in~$\mathbb{R}^d$, 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_1$-) distance. The
problem is NP-hard in 2D and there is no PTAS for 3D
(unless ${\cal P} = {\cal NP}$). Approximation
algorithms are known for 2D, but not for 3D. \par We
present, for any fixed dimension~$d$ and any
$\epsilon>0$, an $O(n^\epsilon)$-approxi\-ma\-tion
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 \ge
2$ parallel planes.},
added-at = {2024-07-14T10:03:47.000+0200},
author = {Das, Aparna and Gansner, Emden R. and Kaufmann, Michael and Kobourov, Stephen and Spoerhase, Joachim and Wolff, Alexander},
biburl = {https://www.bibsonomy.org/bibtex/2fe30167803295cdc46dae57fb048ef1b/awolff},
doi = {10.1007/s00453-013-9778-z},
interhash = {34e06db0e905eb9ef3b024e80dd9a652},
intrahash = {fe30167803295cdc46dae57fb048ef1b},
journal = {Algorithmica},
keywords = {approximation_algorithms computational_geometry minimum_Manhattan_networks myown},
number = 1,
pages = {36--52},
pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/dgkksw-ammnh-Algorithmica13.pdf},
timestamp = {2024-07-14T10:03:47.000+0200},
title = {Approximating Minimum {Manhattan} Networks in Higher
Dimensions},
volume = 71,
year = 2015
}