Efficient algorithm to determine largest open space

Question

I have a situation, brilliantly illustrated below, which requires me to work out the largest circles (open space) within an area. In the below example, the black circles are fixed known positions, I need to find the largest area (represented by the orange and green circles) that doesn't touch the black circles. In the below example the orange circle is the largest open space and this is the area I want to calculate.

I could brute force it, pick a position and expand a circle until it hits a black point, then just record the position and radius of the circle (open space) but this is going to be massively inefficient to iterate through all possible positions.

Is there an efficient way to analyse where the largest open space would be in this instance? Bearing in mind the max number of black points on this field will be 15, but will probably be a lot lower.

EDIT Thanks Yves and all the other commenters. A couple of clarifications based on the answer and other comments. The black box IS a bound, so any area defined must be inside the black box. The radius of the black circles are known and static, however for these purposes they can be reduced to points. Finally, approximation of the circles is acceptable. It will be used in an AI routine that has a margin of error on deciding which area is best anyway. So, if the circle is slightly out in radius or position, it won't be a big issue.

I am currently looking into the Voronoi method and I think I understand it, but now trying to pull an algorithm that fits is the issue! I will test and get back to you.

EDIT 2: Thanks to Yves I looked into the Voronoi diagram and used a simple method of looping through all Voronoi vertices (and points where it crosses the bounding box) and finding the largest circle from that centre point which doesn't contain any of the "black circles". With a relatively small, finite set of points I am happy enough with this implementation. See below for the result, displaying the top 3 empty circles in the space.

Answer 1

This is known as the "largest empty circle" problem. It can be solved efficiently by means of the Voronoi diagram.

If the black circles have a finite diameter, you can shrink them to their center and later deduce the radius from the solution found.

Anyway, if circles are allowed against the rectangle, the algorithm will need to be modified to account for this. A non trivial task.

Update:

A related problem was addressed in "TOUSSAINT, Godfried T. Computing largest empty circles with location constraints. International journal of computer & information sciences, 1983, 12.5: 347-358" and "CHEW, L. Paul; DRYSDALE, Scot. Finding largest empty circles with location constraints. 1986." which describe an efficient solution when the center is constrained to be inside a given convex polygon. (But you are asking for the circle to be wholly contained I guess.)

---

A completely different approach is possible in the digital domain (dealing with a discrete image, pixels of finite size): you can compute the Euclidean distance map to the black pixels. There is a very smart efficient algorithms that achieves that in linear time (wrt the image size, not wrt the number of obstacles); see "A. Meijster, J. B. T. M. Roerdink and W. H. Hesselink, A general algorithm for computing distance transforms in linear time".

After you have computed the distance map, the center of the desired circle is the pixel with the largest distance value. This method will work with obstacles of any shape.

---

Update:

In your case, as the number of obstacle is small, exhaustive search might be acceptable. You need to try the circles passing by 3 points, passing by 2 points and tangent to an edge, or passing by 1 point and tangent to 2 edges.

For all these circles, check that they contains no other point and keep the largest. In principle, this takes time O(N^4). Apparently this complexity can be lowered to O(N³), but every entry I found on this problem describes the Voronoi-based approach and not the exhaustive one.