2
$\begingroup$

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$ Circles with radius

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

$\endgroup$
2
  • $\begingroup$ Let $A$ and $B$ be the top left and bottom right corners of the rectangle. The way if shut if you can get from $A$ to $B$ in the following graph $G$. The vertices of $G$ are $A$, $B$, intersections of circles with circles, and circles with sides of the rectangle. Two vertices $p$ and $q$ are connected by an edge if they belong to the same circle. or if $p$ is either $A$ or $B$ and $q$ is on a side of the rectangle and $p$ is the closets to $q$ among $A$ and $B$. $\endgroup$
    – plop
    Mar 16, 2021 at 16:48
  • $\begingroup$ The graph in my previous comment can be simplified. For example, if $p_1,p_2,...,p_n$ are all vertices on the same circle, then one doesn't need all the edges in the $K_n$ that they will form. It is sufficient to use the edges that are sides of their convex hull, for example. $\endgroup$
    – plop
    Mar 16, 2021 at 16:50

1 Answer 1

4
$\begingroup$

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

Yes instance

No instance (south is connected to west)

No instance, south is connected to west

$\endgroup$
2
  • 1
    $\begingroup$ One way to simplify the cases 1,2,3 into a single one is to consider the top and left sides as a single vertex $A$ and the right and bottom sides as a single vertex $B$. Then a path doesn't exists if there is a path in the graph from $A$ to $B$. $\endgroup$
    – plop
    Mar 16, 2021 at 23:51
  • $\begingroup$ @plop thanks, that made it indeed simpler. Updated. $\endgroup$
    – Pål GD
    Mar 17, 2021 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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