Finding Two Maximum Separating Circles

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 beingapplied in different fields of science, some of which are: facility location, image processing and clustering. Our algorithm findsthe locations of two smallest circles in the plane such that these two circles cover as many as points of Q while avoid the pointsof P. The running time of the algorithm is O(n2), where n is total number of input points. The experimental results show that ouralgorithm succeeds to find near-optimal solutions, with anapproximation factor of 1.32 in average. The proposed algorithm is not optimal, but in some cases it yields optimum solutions

Keywords:

computational geometry , point-set covering , pointset separation