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 language | English (US) |
---|---|
Pages (from-to) | 403-419 |
Number of pages | 17 |
Journal | International Journal of Computational Geometry and Applications |
Volume | 15 |
Issue number | 4 |
DOIs | |
State | Published - Aug 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