Journal of Information Science and Engineering, Vol. 40 No. 4, pp. 865-876

Separating Bichromatic Point Sets by an Axis-Parallel C-shaped Polygon

In the separability problem of bichromatic point sets, given two sets of points colored as blue and red, we want to put a special geometric shape in a manner that includes the blue points while avoiding the red ones. This problem has various applications in data mining and other fields. Separability by various shapes, including L-shaped polygons, has been studied in the literature. In this paper, the separability of bichromatic point sets by C-shaped polygons, which are more general than L-shaped polygons, is studied and an O(nlogn)-time algorithm is presented, where n is the total number of points.

Keywords:
computational geometry, separability, bichromatic point sets, C-shaped polygon, covering