2
$\begingroup$

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.

Example

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?

$\endgroup$
9
  • 1
    $\begingroup$ It'll be one of the vertices of the Voronoi diagram. $\endgroup$
    – user856
    Jun 22 '16 at 15:54
  • $\begingroup$ 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. $\endgroup$ Jun 22 '16 at 15:55
  • $\begingroup$ @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.. $\endgroup$
    – Qwerty
    Jun 22 '16 at 15:58
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Largest_empty_sphere $\endgroup$
    – miracle173
    Jun 22 '16 at 16:20
  • 1
    $\begingroup$ @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)$. $\endgroup$ Jun 22 '16 at 20:21
2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Is there somewhere a proof of the fact you have stated? $\endgroup$
    – Qwerty
    Jun 22 '16 at 16:02
  • $\begingroup$ It's usually left as an exercise to the students. :) Wikipedia cites G. T. Toussaint, "Computing largest empty circles with location constraints," International Journal of Computer and Information Sciences, vol. 12, No. 5, October, 1983, pp. 347-358. $\endgroup$ Jun 22 '16 at 16:06
  • $\begingroup$ Most of the question here were left as an exercise to the students but will be answered here. $\endgroup$
    – miracle173
    Jun 22 '16 at 16:11
  • $\begingroup$ Also, I find Aurenhammer's "Voronoi Diagrams -- A Survey of a Fundamental Geometric Data Structure" in ACM Computing Surveys, 1991, 23, 345-405 quite a useful reference. It mentions Shamos and Hoey 1975 as source. $\endgroup$ Jun 22 '16 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.