Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have a disk of radius $r$, and $n$ points inside this disk, I'm interested in the minimum number of distances $\leq r$ between the points, when the minimum is taken over all $n$ point sets in the (euclidean) plane.

My current worst case construction is to put the points evenly very close to the vertices of a pentagon inscribed into the disk.

Thanks, Stefan

share|improve this question
I think you mean your current best case construction? –  joriki Sep 14 '11 at 4:57
The question seems to me underspecified. Are the points distinct? Why a pentagon? –  Muhammad Alkarouri Sep 14 '11 at 9:35
Are the points distinct? Yes Why a pentagon? Because two vertices of the pentagon have distance > r –  stefan Sep 14 '11 at 12:59
@Muhammad: It doesn't matter whether the points are distinct, since it says $\le$ and you can put them arbitrarily close together, so whatever you can achieve with non-distinct points you can achieve by spreading them out by some small distance. Have you read my proof? If so, why do you nevertheless think that the problem is underspecified? Is there a gap in the proof? –  joriki Sep 14 '11 at 13:04
@joriki: By some quirk of the web site, I wasn't able to see your post. And by some quirk of my mind, I managed to misread the question, and linked it to some work I came across on $\epsilon$-nets. Your proof is correct (as far as I can see). –  Muhammad Alkarouri Sep 14 '11 at 15:05

1 Answer 1

up vote 2 down vote accepted

Here's a proof that your construction is optimal.

Let an optimal construction with $k$ distances $\le r$ be given; let's call such distances "small". If for any pair of points the numbers of small distances they partake of differed by more than $1$, we could move the one with more small distances right next to the other one and improve the construction. It follows that in the optimal construction all points partake of either $\lfloor2k/n\rfloor$ or $\lceil2k/n\rceil$ small distances.

Now pick a point with $\lfloor2k/n\rfloor$ small distances and move all points within $r$ of it so close to it that they're more than $r$ away from all other points. Now they all have $\lfloor2k/n\rfloor$ small distances, and the remaining points all have at most as many small distances as before. Since the construction was optimal, that means that all the points have as many small distances as before. Thus we can apply the same reasoning to the remaining points, and we can keep collapsing groups of points that have $\lfloor2k/n\rfloor$ small distances until there are none left, and then collapse the remaining points into groups with $\lceil2k/n\rceil$ small distances each.

That reduces the problem to finding the maximal number of points in the disk that are all more than $r$ apart and then distributing the remaining points in groups around them. If any of the initial points in such a configuration were not on the boundary, we could move them to the boundary without getting them within $r$ of any of the other points. That reduces the problem to finding the maximal number of points on the boundary that are all more than $r$ apart, and that's obviously $5$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.