Find out if a path exists avoiding circular obstacles

Question

Given

1. a rectangle defined by its corners $(0, 0)$ and $(w,h)$,
2. $n$ circles $\{ (x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ with the same radius $r$,

I need to determine the smallest possible radius r so that there is no way to get from $(0,0)$ to $(w, h)$ without touching those circles.

What I have tried is

1. Use binary search to determine r
2. But the issue is that since there is no limitations for the coordinates of the points (e.g. for them to be integers) I can't get any idea how to construct a graph and use some path finding algorithm such as DFS.

Any help would be appreciated.

---

Examples

Example 1, $w = 15, h = 20$; circles with coordinates $(2,7)$ and $(7,3)$; the result is $d \sim 3.2016$

Example 2 (without the right radius, but just to show what the issue is)

Answer 1

Your assumption using binary search is a good assumption, that means that we can assume we know the radius, and focus only on the subproblem:

Given a rectangle and a set of circles, is it possible to navigate in the rectangle from the top left corner to the bottom right corner without touching a circle.

If a circle is covering either the starting point or the end point, we can abort immediately, so we'll assume they don't.

We will create a graph consisting one vertex for each circle, and one vertex for the south east edges of the rectangle, and one vertex for the north west edges of the rectangle, in other words:

$$V = \{ v_c \mid \text{$c$ is a circle} \} \cup \{v_{\text{se}}, v_{\text{nw}} \}$$

Then we create the edges as follows:

$$E = \{ e = v_{c_1} v_{c_2} \mid \text{$c_1$ and $c_2$ overlap}\} \cup \{ e = v_{c} v_{s} \mid \text{$c$ touches side $s$}\}$$

In other words an edge between two objects if they overlap geometrically.

If the south east sides are connected to the north west sides, then it means that you cannot travel from the lower left part of the rectangle to the upper right part of the rectangle.

In other words, you only need to see whether $v_{\text{se}}$ is connected to $v_{\text{nw}}$ in your constructed graph, which would isolate the starting point from the end point.

---

Yes instance

No instance (south is connected to west)