Dumitrescu, Adrian ;
Tóth, Csaba D.
Long Noncrossing Configurations in the Plane
Abstract
We revisit several maximization problems for geometric networks design
under the noncrossing constraint, first studied by Alon, Rajagopalan
and Suri (ACM Symposium on Computational Geometry, 1993).
Given a set of $n$ points in the plane in general position (no three points collinear), compute a longest noncrossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain new results for (b) and (c), as well as for the Hamiltonian cycle problem:
(i) For the longest noncrossing Hamiltonian path problem,
we give an approximation algorithm with ratio $\frac{2}{\pi+1} \approx 0.4829$. The previous best ratio, due to Alon et al., was $1/\pi \approx 0.3183$. Moreover, the ratio of our algorithm is close to $2/\pi$ on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time.
(ii) For the longest noncrossing spanning tree problem, we give an
approximation algorithm with ratio $0.502$ which runs in $O(n \log{n})$ time. The previous ratio, $1/2$, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first rederive the result of Alon et al. with a faster $O(n \log{n})$time algorithm and a very simple analysis.
(iii) For the longest noncrossing Hamiltonian cycle problem,
we give an approximation algorithm whose ratio is close to $2/\pi$ on a relatively broad class of instances: for point sets with the product
$\bf{\langle}$~diameter~$\times$ ~convex hull size $\bf{\rangle}$ much smaller than the maximum length matching. The algorithm runs in
$O(n^{7/3}\log{n})$ time. No previous approximation results
were known for this problem.
BibTeX  Entry
@InProceedings{dumitrescu_et_al:LIPIcs:2010:2465,
author = {Adrian Dumitrescu and Csaba D. T{\'o}th},
title = {{Long Noncrossing Configurations in the Plane}},
booktitle = {27th International Symposium on Theoretical Aspects of Computer Science},
pages = {311322},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897163},
ISSN = {18688969},
year = {2010},
volume = {5},
editor = {JeanYves Marion and Thomas Schwentick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2465},
URN = {urn:nbn:de:0030drops24655},
doi = {10.4230/LIPIcs.STACS.2010.2465},
annote = {Keywords: Longest noncrossing Hamiltonian path, longest noncrossing Hamiltonian cycle, longest noncrossing spanning tree, approximation algorithm.}
}
09.03.2010
Keywords: 

Longest noncrossing Hamiltonian path, longest noncrossing Hamiltonian cycle, longest noncrossing spanning tree, approximation algorithm. 
Seminar: 

27th International Symposium on Theoretical Aspects of Computer Science

Issue date: 

2010 
Date of publication: 

09.03.2010 