LONG NON-CROSSING CONFIGURATIONS IN THE PLANE

Article type: Research Article

Authors: Alon, Noga | Rajagopalan, Sridhar | Suri, Subhash

Affiliations: Department of Mathematics, Tel Aviv University, Israel | Department of Computer Science, Univ. of California, Berkeley, U.S.A. | Bellcore, Morristown, NJ 07960, U.S.A.

Note: [] Research supported in part by a United States Israel BSF Grant.

Abstract: We study some geometric maximization problems in the Euclidean plane under the non-crossing constraint. Given a set V of 2n points in general position in the plane, we investigate the following geometric configurations using straight-line segments and the Euclidean norm: (i) longest non-crossing matching, (ii) longest non-crossing hamiltonian path, (iii) longest non-crossing spanning tree. We propose simple and efficient algorithms to approximate these structures within a constant factor of optimality. Somewhat surprisingly, we also show that our bounds are within a constant factor of optimality even without the non-crossing constraint, For instance, we give an algorithm to compute a non-crossing matching whose total length is at least 2/π of the longest (possibly crossing) matching, and show that the ratio 2/π between the non-crossing and crossing matching is the best possible. Perhaps due to their utter simplicity, our methods also seem more general and amenable to applications in other similar contexts.

DOI: 10.3233/FI-1995-2245

Journal: Fundamenta Informaticae, vol. 22, no. 4, pp. 385-394, 1995