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
Fingerprint
Dive into the research topics of 'Separating point sets in polygonal environments'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS