Skip to main content
3 of 3
replaced deprecated tag 'geometry'; added relevant tags; minor editing
Ricardo Andrade
  • 6.2k
  • 5
  • 42
  • 69

Determine if circle is covered by some set of other circles

Suppose you have a set of circles $\mathcal{C} = \{ C_1, \ldots, C_n \}$ each with a fixed radius $r$ but varying centre coordinates. Next, you are given a new circle $C_{n+1}$ with the same radius $r$ as the previous circles but with a new centre coordinate.

How can you determine whether the area covered by the $C_{n+1}$ is fully covered by $\mathcal{C}$?

How to do this if the circles can have varying radii?

Note: I couldn't yet work out a nice mathematical solution for this. Coming from computer science, the best I could come up with is solving this in a nasty brute force way using some sort of Monte Carlo sampling, i.e. draw a large number of random points from the area of $C_{n+1}$ and then checking for each point if it is enclosed by at least one circle in $\mathcal{C}_{\text{intersecting}}$ (subset of $\mathcal{C}$ with circles that are within $2r$ of $C_{n+1}$).