4
$\begingroup$

Suppose you have an existing set of circles $\mathcal{C} = {C_1, .., 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 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_{intersecting}}$ (subset of $\mathcal{C}$ with circles that are within $2r$ of $C_{n+1}$).

  • 1
    Crossposted: http://mathoverflow.net/questions/76712/determine-if-circle-is-covered-by-some-set-of-other-circles2011-09-29

1 Answers 1

2

It is easy to check if there is any part at all of the target disk that is covered -- that is just a matter of comparing distances with sums of radii. So assume that there is some overlap.

Now, if there is still also some noncovered area within the target disk, then the boundary of the total cover must pass through the target disk. That boundary consists, almost everywhere, of points that are on the periphery of one of the original disks and not covered by any other of the original disks. (I'm assuming that there are no duplicates among the original disks).

Thus, you can go through the $C_i$'s one by one, and check (a) which range of angles of its boundary is covered by the target disk, and then for each $C_j$ with $i\ne j$ subtract the angle interval on $C_i$'s boundary that is not covered by $C_j$. If there is anything left when you're done, you have found a point on the boundary of the union which is within $C_{n+1}$.

This gives an $O(n^2\log n)$ algorithm. Each angle interval is easily found from distances, radii and relative positions using basic trigonometry.

  • 0
    @Henning: OK, I thin$k$ I didn't fully understand your algorith$m$. I withdraw the co$m$me$n$t.2011-09-29