Paper by Erik D. Demaine

Reference:

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.

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 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.

Comments:

This paper is also available from the ACM Digital Library.

Length:

The paper is 7 pages.

Availability:

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)