Minimizing the Number of Separating Circles for Two Sets of Points in the Plane
Jiaye Wang, Feng Rui Sun, Wenping Wang, Chunyan Miao, Caiming Zhang · 2011
Given two sets of points ℝ and B in the plane, we address the problem of finding a set of circles ℂ = {ci, i = 1, 2,... ,k}, satisfying the condition that every point in ℝ is covered by at least one circle in ℂ and each point in B is not covered by any circle in ℂ. We conjecture that to find such a set with the smallest k is NP-hard. In this paper, we present an approximation algorithm for computing the set with minimal number of such circles. The algorithm finds also a lower bound of the smallest k.