Paper by Erik D. Demaine
- Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides, “Separating point sets in polygonal environments”, International Journal of Computational Geometry and Applications, volume 15, number 4, August 2005, pages 403–419. Special issue of selected papers from the 20th Annual ACM Symposium on Computational Geometry, 2004.
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.
- This paper is also available from WorldSciNet.
- The paper is 16 pages.
- The paper is available in PostScript (1681k), gzipped PostScript (853k), and PDF (234k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ChordSeparation_SoCG2004 (Separating point sets in polygonal environments)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated December 5, 2021 by