Long non-crossing configurations in the plane

Noga Alon, Sridhar Rajagopalan, Subhash Suri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 9th Annual Symposium on Computational Geometry
PublisherPubl by ACM
Pages257-263
Number of pages7
ISBN (Print)0897915828, 9780897915823
DOIs
StatePublished - 1993
Externally publishedYes
EventProceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA
Duration: May 19 1993May 21 1993

Publication series

NameProceedings of the 9th Annual Symposium on Computational Geometry

Other

OtherProceedings of the 9th Annual Symposium on Computational Geometry
CitySan Diego, CA, USA
Period5/19/935/21/93

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Long non-crossing configurations in the plane'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Rajagopalan, S., & Suri, S. (1993). Long non-crossing configurations in the plane. In Proceedings of the 9th Annual Symposium on Computational Geometry (pp. 257-263). (Proceedings of the 9th Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/160985.161145