Crossing families

Boris Aronov, Paul Erdos, Wayne Goddard, Daniel J. Kleitman, Michael Klugerman, János Pach, Leonard J. Schulman

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

    Abstract

    Given n points in the plane, a crossing family is a collection of line segments, each joining two of the points, suck that any two line segments intersect internally. We show that any n points in general position possess a crossing family of size at least √n/12, and describe an O(n logn)-time algorithm for finding one.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Annual Symposium on Computational Geometry
    PublisherAssociation for Computing Machinery
    Pages351-356
    Number of pages6
    ISBN (Print)0897914260
    DOIs
    StatePublished - Jun 1 1991
    Event7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States
    Duration: Jun 10 1991Jun 12 1991

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry

    Other

    Other7th Annual Symposium on Computational Geometry, SCG 1991
    CountryUnited States
    CityNorth Conway
    Period6/10/916/12/91

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Crossing families'. Together they form a unique fingerprint.

  • Cite this

    Aronov, B., Erdos, P., Goddard, W., Kleitman, D. J., Klugerman, M., Pach, J., & Schulman, L. J. (1991). Crossing families. In Proceedings of the Annual Symposium on Computational Geometry (pp. 351-356). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/109648.109687