Separating Multi-Color Points on a Plane with Fewest Axis-Parallel Lines

Article type: Research Article

Authors: Majumder, Subhashis | Nandy, Subhas C. | Bhattacharya, Bhargab B.

Affiliations: Department of Computer Science and Engineering Heritage Institute of Technology Kolkata 700 107, India. E-mail: [email protected] | ACM Unit Indian Statistical Institute Kolkata 700 108, India. E-mail: {nandysc,bhargab}@isical.ac.in

Abstract: In this paper, we deal with the problem of partitioning a set of coplanar points of more than one colors into monochromatic cells using minimum number of axis-parallel straight lines. It is first shown that the problem is NP-hard. A fast heuristic is then presented to solve this problem. Experimental results on randomly generated instances indicate that the proposed method is much faster than the existing techniques, with minor degradation in the cost of the partition.

Keywords: Monochromatic partitioning, NP-hardness, Heuristic, Vertex Cover

DOI: 10.3233/FI-2010-251

Journal: Fundamenta Informaticae, vol. 99, no. 3, pp. 315-324, 2010