7
$\begingroup$

This may be basic to some of you, but excuse my inexperience with comp. geometry:

Given a set of $n$ circles with centers $(x_i, y_i)$ for $1 \leq i \leq n$ and each having radii $r$. Also given a rectangle. All objects are on a plane. How to verify that every point inside the rectangle (including its edges) is fully covered by the circles. That is, each point in the rectangle lay on at least one of the circles.

Anyone have hints ? I am currently trying with voronoi diagrams.

$\endgroup$
  • 1
    $\begingroup$ So one powerful thing to use is $\epsilon$-nets. Create an $\epsilon$-net of the rectangle and check if every element in the net is contained in some disk. I don't know what $\epsilon$ should be in this case, I guess it's $r/2$. $\endgroup$ – Chao Xu Apr 9 '13 at 14:41
8
$\begingroup$

Create a Voronoi diagram on the $n$ disk centers in $O(n\log n)$ time. Intersect it with the rectangle in $O(n)$ time.

Now you have a set of convex shapes, thus the furthest point away from the center of the disk inside the cell is a vertex on the cell. Compute the furthest point for each cell can be done in $O(n)$ time. If for all of them, it is within $r$, then the set of disks covers the rectangle.

A $O(n \log n)$ algorithm.

$\endgroup$
  • $\begingroup$ Yes, this correct. It can be proven by contradiction. $\endgroup$ – AJed Apr 10 '13 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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