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

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.

Comments:

This paper is also available from WorldSciNet.

Length:

The paper is 16 pages.

Availability:

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)