Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$).

share|improve this question
1  
Crossposted: mathoverflow.net/questions/76712/… –  Byron Schmuland Sep 29 '11 at 2:21
add comment

1 Answer

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.

share|improve this answer
    
I'm not sure if I fully understand. Correct me if I'm wrong, but doesn't this only check that the boundary of the target disk is covered by original disks and not the whole area of the target disk? –  Adrian Schönig Sep 29 '11 at 3:35
    
No -- you're checking for each original disk that the part of ITS boundary that is inside the target disk is also covered by other original disks. If that is true, you get the entire target disk for free. –  Henning Makholm Sep 29 '11 at 4:43
    
@Henning: Is there not an issue concerning the number of angle ranges that must be maintained at any stage of the algorithms? To achieve $O(n^2)$ overlall, that needs to be $O(n)$ at each stage. I believe this is true, but for non-obvious reasons. –  Joseph O'Rourke Sep 29 '11 at 12:00
    
@Joseph: I think it is fairly obvious that there'll be at most $2n$ endpoints at any time -- you start out with 2 for the intersection with the target circle, and each intersection with a peer adds at most 2 endpoints. But I probably should introduce a $\log n$ factor for organizing the up to $n$ subintervals in a tree. –  Henning Makholm Sep 29 '11 at 17:26
    
@Henning: OK, I think I didn't fully understand your algorithm. I withdraw the comment. –  Joseph O'Rourke Sep 29 '11 at 20:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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