Minimizing the number of separating circles for two sets of points in the plane

Given two sets of points ℝ and double-struck B in the plane, we address the problem of finding a set of circles ℂ = {c i, i = 1, 2,...,k}, satisfying the condition that every point in ℝ is covered by at least one circle ℂ and each point in double-struck B is not covered by any circle ℂ. We conjecture that to find such a set with the smallest k is NP-complete. 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. © 2011 IEEE.link_to_subscribed_fulltex