JISE


  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]


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


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


FATEMEH KESHAVARZ-KOHJERDI1,+, ANITA SHEYBANI2
AND ALIREZA BAGHERI2
1Department of Computer Science
Shahed University
Tehran, 3319118651 Iran
E-mail: f.keshavarz@shahed.ac.ir

2Department of Computer Engineering
Amirkabir University of Technology (Tehran Polytechnic)
Tehran, 1591634311 Iran
E-mail: {sheybani.anita; ar bagheri}@aut.ac.ir


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

  Retrieve PDF document (JISE_202404_11.pdf)