The Stack Overflow podcast is back! Listen to an interview with our new CEO.

 2 added 13 characters in body edited Apr 10 '13 at 4:20 Chao Xu 1,6681111 silver badges3030 bronze badges Create a Voronoi diagram on the $$n$$ circlesdisk 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 point incenter 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 total of $$O(n \log n)$$ algorithm. Create a Voronoi diagram on the $$n$$ circles 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 point in 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 total of $$O(n \log n)$$ algorithm. 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. 1 answered Apr 9 '13 at 14:47 Chao Xu 1,6681111 silver badges3030 bronze badges Create a Voronoi diagram on the $$n$$ circles 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 point in 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 total of $$O(n \log n)$$ algorithm.