Finding Two Maximum Separating Circles

Abstract

In this paper, for the first time an algorithm is presented for separating the points by two circles. Separating the points by circles is one of the problems in computational geometry being applied in different fields of science, some of which are: facility location, image processing and clustering. Our algorithm finds the locations of two smallest circles in the plane such that these two circles cover as many as points of Q while avoid the points of P. The running time of the algorithm is O(n2), where n is total number of input points. The experimental results show that our algorithm succeeds to find near-optimal solutions, with an approximation factor of 1.32 in average. The proposed algorithm is not optimal, but in some cases it yields optimum solutions.