Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 10-16, 2004.

- Download SoCG verison (© 2004 ACM):
- Official SoCG version from ACM's Digital Library (subscription or $5 payment required)

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 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 (jeffe@cs.uiuc.edu) 07 Jul 2004