1
$\begingroup$

I want to know how many points ($n$) can be placed in a circle of radius $r$, with a minimum spacing $s$ between points. I find postings for several similar problems -- smallest circle around a set of points, packing circles, etc -- but not for this case.

Clearly it's not simple. I'm pretty sure the following are correct but have not attempted proofs, as I'll be happy with a reasonable degree of certainty:

For $r<\frac{s}{2}$, $n=1$. The one point can be placed anywhere in the circle.

For $r\geq \frac{s}{2}$ and $r<\frac{s}{\sqrt{3}}$, $n=2$. When $r=\frac{s}{2}$, the points must be at opposite ends of a diameter.

For $r\geq \frac{s}{\sqrt{3}}$ and $r<\frac{s}{\sqrt{2}}$, $n=3$. When $r=\frac{s}{\sqrt{2}}$, the points must be equally spaced on the circumference of the circle.

For $r\geq \frac{s}{\sqrt{2}}$ and $r<\frac{s}{2}\times \tan(54^\circ)$, $n=4$. Again, the smallest value of $r$ requires equal spacing on the circumference. Perhaps there's a better expression for the upper bound.

For $r\geq \frac{s}{2}\times \tan(54^\circ)$ and $r<s$, $n=5$.

Now it gets fun, because when $r=s$, $n=7$. That's one point in the center and six points equally spaced around the circumference. There is no value of $r$ for which n=6. This means there is no continuous function which when rounded gives n as a function of $r$ for all positive values of $r$.

Then of course it gets even more complicated. I'm pretty sure that the next step is $n=8$, with a point in the center and seven points around the circumference. It's tempting to think that at some point one could turn alternate points in, making sort of a star and possibly reducing the diameter. I don't have an argument, but my inclination is to think this does not happen: that you keep adding points one at a time, through $n=12$ points -- one in the center and $1$ around the circumference -- and then, suddenly, it jumps to $n=19$, because $12$ points on the circumference allows both the center point and the first ring of $6$.

Perhaps this would lead to a system: divide the range ($r$) into $ds\leq r< (d+1\times s)$, with a continuous formula (rounded) within each division. But I'm getting a headache. It's been over $40$ years since I did this sort of stuff to get my degree.

Oh, the application is geocaching. Geocaches must be placed a minimum distance apart: $s = 0.1$ mile. I'm writing a program (a GSAK macro to be specific) which needs to download all the geocaches within a specific distance ($r$) of a given latitude and longitude. The only reasonable way of invoking the download requests a number of geocaches, not a radius. But I don't want to make an overkill request, because the user running the macro has an allocation of downloads/day. Therefore I'd like to make the request for the maximum number, but no more. (There's another entry in the API which might enable a continuation call, but I'm not sure and it's vastly more complicated to use.)

Of course geocaches are placed on the surface of a sphere, the earth, so technically the analysis should be done in spherical geometry. (The minimum spacing requirement in geocaching ignores elevation.) But $r$ will be vary small (typically less than a mile) compared to the size of the earth, and this combined with the errors inherent in measurements in the game make Euclidean geometry sufficient for the purpose.

Edward

$\endgroup$
  • $\begingroup$ The Wikipedia page for the Thomson problem may be of interest, along with the links therein. $\endgroup$ – Semiclassical Sep 9 '14 at 23:35
2
$\begingroup$

Equivalently you are asking about how to place $n$ disks of radius $s/2$ inside a circle of radius $r+s/2$. Erich's Packing Center has a list for this which covers cases where $n\le20$, so as long as $\frac{2r+s}{s}\lessapprox5.122$ you can read a likely number from that list. But only some of the figures in that list come with an actual proof, for other numbers these are simply the best known solutions (at least at the time that list was written and to the knowledge of its author).

$\endgroup$
  • $\begingroup$ Thank you. Yes, I had considered packing circles, but I missed the way of making them equivalent by extending the radius. And thank you for the link. Makes it clear that the situation is even more complex than I thought. For 1 <= n <= 9, and for n=19, I was correct. It gets really interesting from 10 to 18. And there's no indication of a general counting function. I can probably set an upper limit of 20 on the downloads anyway, so Erich's list probably goes far enough for this purpose. It's been interesting though. $\endgroup$ – paleolith Sep 10 '14 at 17:42

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.