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”, in Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004), Brooklyn, New York, June 9–11, 2004, pages 10–16.
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 which separate the two sets; when they exist we also
derive efficient algorithms for their obtention. We study as
well the separation of the two sets using a minimum number
of pairwise non-crossing chords.
- This paper is also available from the ACM Digital Library.
- The paper is 7 pages.
- The paper is available in PostScript (1639k), gzipped PostScript (834k), and PDF (237k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- ChordSeparation_IJCGA (Separating point sets in polygonal environments)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated June 7, 2021 by