Approximating Minimum Manhattan Networks in Higher Dimensions

Details Approximating Minimum Manhattan Networks in Higher Dimensions Approximating Minimum Manhattan Networks in Higher Dimensions

2011-07-05

arxiv.org/abs/1107.0901v1

Computer Science

Computational Geometry

Scientific paper

We consider 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. We present, for any fixed dimension $d$ and any $\epsilon>0$, an $O(n^\epsilon)$-approximation. For 3D, we also give a $4(k-1)$-approximation for the case that the terminals are contained in the union of $k \ge 2$ parallel planes.

Affiliated with

Also associated with

No associations

Rating

Approximating Minimum Manhattan Networks in Higher Dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximating Minimum Manhattan Networks in Higher Dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating Minimum Manhattan Networks in Higher Dimensions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-477518