2
$\begingroup$

What is the maximum number of points we can place in the plane so that the distance between any two such points is in the interval $[1,a]$?

I had initially conjectured that the maximum could be found by trying with regular $n$-gons of side $1$ until the largest diagonal exceeded $a$.

However I have recently found this to be false. Placing $7$ points with distances in $[1,2]$ is possible by taking a hexagon of side length $1$ and placing one point on each vertex and one in the center of the hexagon. On the other hand a heptagon of side length $1$ has its largest diagonals of length approximately $2.246$.

What is the maximum number of points we can place given $a$? Is there a neat construction which achieves this all the time?


Also note that if we can solve this problem then we can solve the problem of placing $n$ Points on the plane so as to maximize the number of pairs of points $(a,b)$ at distance between $1$ and $a$. This is because if we know the maximum possible clique we can build the Turan Graph by placing a lot of points in the same place.

$\endgroup$

1 Answer 1

2
$\begingroup$

This belongs to a wide class of packing problems that are quite hard to solve.

Anyway, some heuristics are quite easy. If we take $n$ points inside a unit circle, with respect to a uniform probability distribution, we expect that the most distant points are two units apart and the infimum of the distances is around $\frac{2}{\sqrt{n}}$.

So, assuming that $a$ is big, we expect to be able place around $a^2$ points in such a way that their distances lie in $[1,a]$, but not much more.

$\endgroup$
2
  • $\begingroup$ Thanks! Do you have any references? $\endgroup$
    – Asinomás
    Commented Jun 4, 2015 at 15:13
  • $\begingroup$ @Gamamal: not at hand, but I bet that by googling something like "probabilistic arguments for circle packing" you can find interesting material. $\endgroup$ Commented Jun 4, 2015 at 15:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .