Effective algorithm for determining the largest open space

Question

I have a situation, brilliantly illustrated below, which requires me to develop the largest circles (open space) within the area. In the example below, black circles fix known positions, I need to find the largest area (represented by orange and green circles) that does not touch the black circles. In the example below, the orange circle is the largest open space, and this is the area I want to calculate.

I could go over it, select a position and turn the circle around until it reaches a black point, and then just write down the position and radius of the circle (open space), but it will be massively inefficient for repeating all possible positions.

Is there an effective analysis method, where in this case there will be the largest open space? Given that the maximum number of black dots in this field will be 15, but will probably be much lower.

EDIT Thanks to Eve and all the other commentators. A few clarifications based on the answer and other comments. A black box is required, so any specific area must be inside the black box. The radius of the black circles is known and static, but for these purposes they can be reduced to points. Finally, approaching circles is acceptable. It will be used in the AI ​​procedure, which has a margin of error in determining which region is best in any case. So, if the circle is slightly pulled out in a radius or position, this will not be a big problem.

I am currently studying the Voronoi method, and I think I understand this, but now trying to pull out an algorithm that fits is the problem! I will check and get back to you.

EDIT 2 . Thanks to Jus, I looked at the Voronoi diagram and used the simple loop method through all the Voronoi vertices (and the points where it intersects the bounding box) and finding the largest circle of it that does not contain any of the “black circles”. With a relatively small, finite set of points, I am quite satisfied with this implementation. Below is a result showing the top 3 empty circles in space.

Answer 1

This is called the "big empty circle" problem. It can be effectively solved using the Voronoi diagram.

If the black circles have a finite diameter, you can squeeze them to the center, and then derive the radius from the solution found.

In any case, if the circles are allowed against the rectangle, you need to change the algorithm for this. Non-trivial task.

Update

A related issue was addressed in TOUSSAINT, Godfried T. Computing the largest empty circles with location restrictions. International Journal of Computer and Information Sciences, 1983, 12.5: 347-358 and CHEW, L. Paul, DRYSDALE, Scot. Search for the largest empty circles with location restrictions. 1986. "which describe an effective solution when the center is bounded inside a given convex polygon. (But you ask that the circle be completely complex, I think.)

---

In a digital domain (related to a discrete image, pixels of a finite size), a completely different approach is possible: you can calculate the Euclidean map of the distance to black pixels. There are very smart efficient algorithms that achieve this in linear time (by image size, not by the number of obstacles); see "A. Meijster, JBTM Roerdink and WH Hesselink, General Algorithm for Calculating Distance in Linear Time."

After calculating the distance map, the center of the desired circle will be the pixel with the largest distance value. This method will work with obstacles of any shape.

---

Update

In your case, since the number of obstacles is small, an exhaustive search may be acceptable. You need to try circles that go through 3 points, go through 2 points and are tangent to an edge, or go through 1 point and tangent to two edges.

For all of these circles, make sure they don't contain any other point and keep the largest. In principle, it takes O (N ^ 4) time. Apparently, this complexity can be reduced to O (N³), but every entry I found on this problem describes a Voronoi-based approach, not an exhaustive one.