# Largest enclosed (inscribed) circle in cloud of points

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?

• It'll be one of the vertices of the Voronoi diagram.
– user856
Jun 22 '16 at 15:54
• Any subset of three points will determine a triangle, and using the Pythagorean theorem and the coordinates of the pufnts, you can find the side lengths of the triangle. There is a formula for the circumradius of a triangle in terms of only the three side lengths. I think it may be worth trying some sort of constrained maximization of the circumradius. Jun 22 '16 at 15:55
• @ZubinMukerjee Take 3 adjacent points . They form a triangle. Their cirum radius is one of the smallest. But it is much smaller than what the OP desires.. Jun 22 '16 at 15:58
• en.wikipedia.org/wiki/Largest_empty_sphere Jun 22 '16 at 16:20
• @AugSB: If $(x_b, y_b)$ is the center of the axis-aligned bounding box for the points, can you guarantee that the distance $d_i$ between that point and each point $(x_i, y_i)$ fulfills $r_{min} \le d_i \le r_{max}$ with $r_{min} \gt 0$? (I.e., the points are scattered in a ring, with, say, at least one point in each octant of the ring.) If so, there might be some easy speedups. In particular, I do believe the center of the incircle is then within $r_{max}-r_{min}$ from point $(x_b,y_b)$. Jun 22 '16 at 20:21