TY - GEN

T1 - Long non-crossing configurations in the plane

AU - Alon, Noga

AU - Rajagopalan, Sridhar

AU - Suri, Subhash

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 1993

Y1 - 1993

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027870266&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027870266&partnerID=8YFLogxK

U2 - 10.1145/160985.161145

DO - 10.1145/160985.161145

M3 - Conference contribution

AN - SCOPUS:0027870266

SN - 0897915828

SN - 9780897915823

T3 - Proceedings of the 9th Annual Symposium on Computational Geometry

SP - 257

EP - 263

BT - Proceedings of the 9th Annual Symposium on Computational Geometry

PB - Publ by ACM

T2 - Proceedings of the 9th Annual Symposium on Computational Geometry

Y2 - 19 May 1993 through 21 May 1993

ER -