Finding Two Maximum Separating Circles

Afsaneh Hellatabadi Farahani, Alireza Bagheri


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.


computational geometry; point-set covering; point-set separation

Full Text:


Lululemon Black Friday cheap nfl jerseys Lululemon factory Outlet ny Black Friday discount tiffany outlet wholesale soccer jerseys online oakley black friday cheap nhl jerseys china cheap nfl jerseys north face black friday sale cheap nfl jerseys online Jordans Black Friday Sale 2015 Cheap Moncler Cyber Monday moncler outlet cheap soccer jerseys moncler outlet black friday cheap authentic nfl jerseys north face cyber monday Louboutin Black Friday canada wholesale cheap nfl jerseys lululemon cyber monday 2015 cheap nfl jerseys from china 2015 Cheap Moncler Black Friday Sale Moncler Cyber Monday 2015 cheap jerseys Lululemon Cyber Monday Sale jordans cyber monday deals 2015 Black Friday deals Lululemon 2015 jordan black friday 2015 Moncler Jackets Black Friday Sale 2015 Louboutin Pas Cher Black Friday 2015 Canada Lululemon north face black friday cheap wholesale soccer jerseys