Source author record

Aparna Das

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2012arXiv

Approximating Minimum Manhattan Networks in Higher Dimensions

We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called \emph{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 ${\cal P}={\cal NP}$ ). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension $d$ and any $\eps>0$, an $O(n^\eps)$-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 \ge 2$ parallel planes.

preprint2012arXiv

Polylogarithmic Approximation for Generalized Minimum Manhattan Networks

Given a set of $n$ terminals, which are points in $d$ -dimensional Euclidean space, the minimum Manhattan network problem (MMN) asks for a minimum-length rectilinear network that connects each pair of terminals by a Manhattan path, that is, a path consisting of axis-parallel segments whose total length equals the pair's Manhattan distance. Even for $d=2$ , the problem is NP-hard, but constant-factor approximations are known. For $d \ge 3$ , the problem is APX-hard; it is known to admit, for any $\eps > 0$, an $O(n^\eps)$-approximation. In the generalized minimum Manhattan network problem (GMMN), we are given a set $R$ of $n$ terminal pairs, and the goal is to find a minimum-length rectilinear network such that each pair in $R$ is connected by a Manhattan path. GMMN is a generalization of both MMN and the well-known rectilinear Steiner arborescence problem (RSA). So far, only special cases of GMMN have been considered. We present an $O(\log^{d+1} n)$ -approximation algorithm for GMMN (and, hence, MMN) in $d \ge 2$ dimensions and an $O(\log n)$ -approximation algorithm for 2D. We show that an existing $O(\log n)$ -approximation algorithm for RSA in 2D generalizes easily to $d>2$ dimensions.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.