Problem Detail: 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.
Asked By : AJed
Answered By : Chao Xu
Create a Voronoi diagram on the $n$ disk centers in $O(nlog 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11163 Ask a Question Download Related Notes/Documents
