Academic
Publications
Long Non-crossing Configurations in the Plane

Long Non-crossing Configurations in the Plane,10.1007/s00454-010-9277-9,Discrete & Computational Geometry,Adrian Dumitrescu,Csaba D. Tóth

Long Non-crossing Configurations in the Plane   (Citations: 1)
BibTex | RIS | RefWorks Download
We revisit some maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1995). Given a set of n points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching, (b) a Hamiltonian path, and (c) a spanning tree. We obtain some new results for (b) and (c), as well as for the Hamiltonian cycle problem. (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio . The previous best ratio, due to Alon et al., was . The ratio of our algorithm is close to on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. For instance “random” point sets meet the condition with high probability. The algorithm runs in O(n 7/3log n) time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio 0.502 which runs in O(nlog n) time. The previous ratio, 1/2, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to 2/π on a relatively broad class of instances: for point sets where the product 〈diameter×convex hull size〉 is much smaller than the maximum length matching. Again “random” point sets meet the condition with high probability. However, this algorithm does not come with a constant approximation guarantee for all instances. The algorithm runs in O(n 7/3log n) time. No previous approximation results were known for this problem.
Journal: Discrete & Computational Geometry - DCG , vol. 44, no. 4, pp. 727-752, 2010
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: