# Minimum number of points to intersect any circle in the region

Fix some $r$, $x$, and $y$.

Suppose you have a rectangular region measuring $x \times y$. You can place a circle of radius $r$ anywhere in the region.

You want to place points in the region such that regardless of where you place the circle within the region, the circle will intersect at least one of the points in the region.

The question is: what is the minimum number of points, depending on $r,x,y$? Clearly some arrangements of points are more efficient than others. (For what it's worth: I'm trying to find the most efficient arrangement -- the actual closed-form expression for the minimum number of points is of secondary importance.)

I'm not sure if this is helpful, but points placed on the border of the region do not count. You can assume that if the circle intersects the border, that counts as it intersecting a point.

Thus far, the best arrangement of points I found was a grid where we space points with a distance of $r\sqrt{2}$. The idea here is that such spacing yields a distance of $2r$ (i.e. the diameter of the circle) between points that are diagonal to one another.

I think this is the optimal arrangement for a grid, but I'm curious if there are better non-grid arrangements. I think of this as intuitively related to covering problems (I would appreciate help developing this line of thought), and I know that for circle packing, a hexagonal tiling is optimal. I'm wondering if there's a similar solution here.

You want that every point in your rectangle has a distance of at most $$r$$ to at least one of the points from your set. Which means that the whole rectangle should be covered by circles of radius $$r$$ centered around your points, which makes this a covering problem. Covering problems are usually dual to packing problems, so your comparison to circle packing was already going in the right direction.
• @Newb: I'd assume that covering rectangles and disks is comparable in terms of complexity. EPC lists other covering problems as well, including circles covering circles. MathWorld has a page on that as well. So for small numbers the problem is apparently reasonably well understood, but even for $n=6$ there appears to be no proof of optimality.