I have a set of points that approximately lie on a circle. I would like to compute the largest circle that does not contain any of the points.
Of course, one could draw the circle far away from the points and this would be even bigger thatn the one drawn in the picture above. Of course, that type of circles cannot be taken into account; the circle should be centered inside the set.
In the case of enclosing circles and spheres, I have read that there exists a nice efficient algorithm by Emo Welzl, described in his paper Smallest enclosing disks(balls and ellipsoids). Could this be adapted to the largest enclosed circle? Is there any other algorithm that can be used to solve this problem?
Any hint, reference, keyword to look up… is really welcome. Thanks!
EDIT: It seems that Voronoi Diagrams are the suggested option to solve this. The examples by miracle173 seem to refer to any type of point cloud. Is there any way to speed up the computation, taking into account that the points form, approximately a circle?
Best Answer
Compute the Voronoi Diagram of your point set. The center of the largest inscribed circle will be on one of the (linearly many) Voronoi nodes.
To compute the VD, you could for instance use CGAL.