2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

There should be ample literature on that. For example, Covering a Rectangle With Equal Circles and Covering a rectangle with six and seven circles apparently discuss cases for up to 7 circles, focusing on optimality. Covering a compact polygonal set by identical circles looks for local optima in a more general setup. Overview articles like Packing, covering and tiling in two-dimensional spaces might provide useful pointers. I haven't read any of these, just searched on Google Scholar. The message is that these problems are really hard to solve with guaranteed optimality, but they are the subject of research.

This page has an illustrated listing of ways to cover squares with a given number of circles of minimal radius, using up to 12 circles. It may give you an idea about the configurations to expect. Most of them do not follow a regular grid, although the irregularities are more prononunced for some numbers of circles than for others. If you expect a large number of circles and want to go for a regular grid, you should choose a hexagonal grid, since that has less overlap between adjacent circles. When covering the whole plane, this is optimal, and so for rectangles which are large compared to the radius, this should still be close to optimal.

Comparison of square and hexagonal grid

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Based on the links you provided, I take it that this problem is much harder in other shapes? E.g. instead of a rectangle, doing the covering in a circle? $\endgroup$ – Newb Sep 2 '16 at 8:32
  • $\begingroup$ @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. $\endgroup$ – MvG Sep 2 '16 at 9:13

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.