SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
Erik D. Demaine, Jeff Erickson, Ferrán Hurtado, John Iacono, Stefan Langerman, Henk Meijer, Mark Overmars, Sue H. Whitesides · International Journal of Computational Geometry & Applications · 2005
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.