Placing a circle in a plane without overlap

Question

Given are $n$ non-overlapping unit circles in $\mathbb R^2$ and some number $r>1$. Let $C$ be one of the circles. I want to place a new circle of radius $r$ which is tangent to $C$ and additionally does not overlap any of the other circles.

How can I find a suitable center for this new circle efficiently, or at least decide whether this is even possible or not?

Answer 1

Hint:

You can solve this using a trick: instead of placing circles of radius $r$ tangent to a given circle, you can inflate all circles by $r$ and place a point on the circumference of that circle.

This implies to compute the union of the inflated circles, a relatively complex geometric operation. When this is done, for every circle that still has a piece of circumference in this "union map", the answer is positive.

https://mathoverflow.net/questions/24859/finding-the-union-of-n-random-circles-arbitrarily-or-conspiratorially-placed-o

Answer 2

In the picture below, suppose $C$ is the circle in black, while the other circles are in grey. Surround $C$ with a concentric red circle radius $1+r$ and the other circles with pink circles radius $1+r$.

Any point on the red circle can be the centre of a new circle of radius $r$ which is tangent to $C$. Any point not inside a pink circle can be the centre of a new circle of radius $r$ which does not overlap a grey circle.

So any point on the red circle not in a pink circle (reshaded blue) can be the centre of a new circle of radius $r$ which is tangent to $C$ and additionally does not overlap any of the other grey circles. If there are no such points (i.e. if the red circle is covered by the pink circles), then it is not possible.

Answer 3

Let the pivot circle $C$ be placed at the origin $O$.

Then among the centers of the other circles, let's choose the two nearest to $O$, say $A,B$.

Let's draw the circle circumscribing the three point, having center $C_c$ and radius $R$. The maximum circle that we can fit will have center $C_c$ and radius $r=R-1$.

Now, it is possible that inside the circumscribing circle there might be a fourth point $D$ which, although being farer from $O$ than $A$, will define with $O,B$ a smaller circum-circle.
In that case we will choose that, and repeat the check.