| Universitat Polit`ecnica de Catalunya Polytechnic University (2008) | |||||||||||||||
Abstract | |||||||||||||||
| 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 for their obtention. We study as well the separation of the two sets using a minimum number of pairwise non-crossing chords. Categories and Subject Descriptors: F.2.2 [Nonnumerical Algorithms and Problems] | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||