Separating point sets in polygonal environments

Written with Erik D. Demaine, Ferran Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, and Sue Whitesides.

Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 10-16, 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 which separate the two sets; when they exist we also derive efficient algorithms to compute them. We study as well the separation of the two sets using a minimum number of pairwise non-crossing chords.

Publications - Jeff Erickson ( 07 Jul 2004