Separating Several Point Sets in the Plane
Olivier Devillers, Ferrán Hurtado, Mercè Ferrater Mora, Carlos Seara · 2001
In this paper we study some problems on the separability of k disjoint point sets in the plane. On one hand, we give algorithms for nding minimum-cardinality separators by means of parallel lines or rays with common apex. On the other hand we show how to decide whether it is possible to separate by k 1 parallel lines, k rays with same origin, an arrangement of 23 lines or, in the projective sense, by k lines through a point. Keywords : Separation, discrimination, classi cation. 1