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.

Cheesy

Is the black box also a bound, or are the colored circles supposed to be bounded only by the black circles? – Pleura

Do all the black circles have the same radius? – Pleura

I feel like somewhere off to the right has more open space than where the orange circle is – Fassold

brilliantly illustrated below haha – Parley

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.

Stillman

Can the border not be made out of the black circles? – Fassold

@cricket_007: yes, but you'll need an infinite number of them :( – Stillman

Why infinite? Just line them up so the diameters touch. A pixel is a finite value. – Fassold

Doing that, the boundary that you get isn't straight and the solutions will slightly go over the rectangle. You can do it if an approximate solution is allowed. (Pixels are square, not round.) – Stillman

In practice, "a lot of points equally spaced along a line" is very often a good approximation for a straight line. And often an approximate answer is good enough. In fact, almost all non-integer numeric computations on computers are approximations. But it's good to be clear about what kind of approximation you are willing to accept. – Pascal

@DavidK: in the computational geometry community, the algorithms are by default exact (computations are assumed to have infinite accuracy; this is why implementors often strive with extended precision arithmetic). When you relax this requirement, you explicitly qualify the algorithm as approximate. – Stillman

@YvesDaoust Your last sentence is what I meant by "it's good to be clear". "Very often" is not "always" (or even necessarily "usually"). Also, while even extended-precision is still an approximation, the existence of one source of possible loss of precision is not an excuse for ignoring other sources. When someone does accept an approximation, they should specify what approximation they are accepting. – Pascal

By the way, in the figure given as an example, I think even ordinary double-precision arithmetic would introduce orders of magnitude less error than replacing the straight lines with chains of circles would. That is, the inherent precision of floating-point arithmetic is not really the problem here. – Pascal

@DavidK: multiple precision isn't used to return very precise coordinates, but to ensure that the solution is correct in a combinatorial sense (in this particular case, the same three tangency points found as if arithmetic was perfect). In an approximate approach, returning wrong points would be allowed. – Stillman

Good point. If the two largest circles are along the boundary and are almost exactly the same size, a "bumpy" boundary might choose the wrong circle as its "solution." With sufficient (but finite) precision, this can be detected by an exact algorithm. Here the difference between the exact and approximate algorithms is not just in some relatively insignificant bits, it could be the difference between putting the circle along the left edge or along the right edge. – Pascal

@anothershrubery: curious to know what approach you took. (Ni!) – Stillman

@Yves: Have a look at my final edit there, thanks for the advice. (PS. Good to see you get the reference!) ;) – Cheesy

@anothershrubery: well done ! Beware that with this method you will find large empty circles but you can miss the largest when it is against a wall. – Stillman

@Yves: Yeah I realise that, but it is efficient enough and a good enough approximation of the space for the purpose. Cheers. – Cheesy