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: Contribution to journalArticlepeer-review


    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 that separate the two sets; when they exist we also derive efficient algorithms for their obtention. We also study the separation of the two sets using the minimum number of pairwise non-crossing chords.

    Original languageEnglish (US)
    Pages (from-to)403-419
    Number of pages17
    JournalInternational Journal of Computational Geometry and Applications
    Issue number4
    StatePublished - Aug 2005


    • Chord
    • Geodesic
    • Separation
    • Simple polygon

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Theory and Mathematics
    • Computational Mathematics
    • Applied Mathematics


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

    Cite this