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 journalArticle

Abstract

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
Volume15
Issue number4
DOIs
StatePublished - Aug 1 2005

Keywords

  • Chord
  • Geodesic
  • Separation
  • Simple polygon

ASJC Scopus subject areas

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

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

  • Cite this

    Demaine, E. D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Meijer, H., Overmars, M., & Whitesides, S. (2005). Separating point sets in polygonal environments. International Journal of Computational Geometry and Applications, 15(4), 403-419. https://doi.org/10.1142/S0218195905001762