Separating point sets in polygonal environments

Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, Sue Whitesides

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


    We consider the separability of two point sets inside a polygon by means of chords or geodesic lines. Specifically, given a set of red points and a set of blue points in the interior of a polygon, we provide necessary and sufficient conditions for the existence of a chord and for the existence of a geodesic path which separate the two sets; when they exist we also derive efficient algorithms for their obtention. We study as well the separation of the two sets using a minimum number of pairwise non-crossing chords.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
    Number of pages7
    StatePublished - 2004
    EventProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04) - Brooklyn, NY, United States
    Duration: Jun 9 2004Jun 11 2004


    OtherProceedings of the Twentieth Annual Symposium on Computational Geometry (SCG'04)
    Country/TerritoryUnited States
    CityBrooklyn, NY


    • Chords
    • Geodesies
    • Polygons
    • Separability

    ASJC Scopus subject areas

    • Software
    • Geometry and Topology
    • Safety, Risk, Reliability and Quality
    • Chemical Health and Safety


    Dive into the research topics of 'Separating point sets in polygonal environments'. Together they form a unique fingerprint.

    Cite this