Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 10-16, 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 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.