19 points on a hexagon

Question

What is the optimal (i.e., smallest) constant $\alpha$ such that, given 19 points on a solid, regular hexagon with side 1, there will always be 2 points with distance at most $\alpha$?

This is a reformulation of an interesting question that was mercilessly downvoted.

I can show the bounds $1/2 \leq \alpha\leq 1/\sqrt{3}$.

To show the upper bound, divide the hexagon into 6 regular triangles with sides 1 and note that one of them must contain 4 points.

To show the lower bound, divide the hexagon into 24 regular triangles with sides 1/2 and draw a point at each of the 19 corners.

Addition. Here's an idea: Let $\Omega$ be a subset of the plane obtained by gluing together regular, side-1 triangles side-to-side. Let $n$ be the total number of corners. Then the only way of placing $n$ or $n-1$ points on $\Omega$ such that no 2 points are closer than 1 is by placing the points at the corners. Proof: Induction on the number of triangles.

Answer 1

$\alpha=\frac{1}{2}$ is the optimal bound. We just need to prove that for every $\varepsilon>0$ we can take $19$ points in the hexagon such that the distance between any two of them is $\geq\frac{1}{2}-\varepsilon$. Easily done: we place $19$ points in a regular hexagon width side length $1-\delta$ accordingly to the given construction, then apply a homothety bringing the $(1-\delta)$-hexagon into a unit hexagon. Any two "scaled" points inside the unit hexagon will be separated by a distance $\geq \frac{1}{2(1-\delta)}$, so $\alpha\geq\frac{1}{2}$ follows from taking: $$\delta = \frac{2\varepsilon}{1+2\varepsilon}.$$ To prove $\alpha\leq\frac{1}{2}$, we split the original unit hexagon in $18$ congruent cyclic quadrilaterals (boundaries in red): Now, if eight or more points fall in the innermost hexagon, we are ok since we can cover the innermost red hexagon with seven polygons having diameter $\frac{1}{2}$. This gives that we can assume that there are at most seven points in the innermost hexagon, then at least twelve points in the outermost annulus. Since the perimeter of the external boundary of the annulus is six, even in this case there are $2$ points at most $\frac{1}{2}$-apart.

---

A simple measure-theoretic argument provides a little weaker bound. Assuming that we can place $21$ points inside a unit hexagon in such a way that the distance between any two of them is $\geq\frac{1}{2}$, then we can fit $21$ circles with radius $\frac{1}{4}$, without any overlapping, inside a regular hexagon with side length $1+\frac{1}{4}$. However, that gives a contradiction since: $$ 21\cdot\frac{\pi}{16}>\frac{3\sqrt{3}}{2}\left(1+\frac{1}{4}\right)^2, $$ so in the unit hexagon we can place at most $20$ points in such a way that the distance between any two of them is $\geq\frac{1}{2}$. I hope someone is able to improve this argument to show that to place $20$ circles is also impossible.

Answer 2

(From my answer to the same question on Quora, 2014-03-04.)

Draw non-overlapping circles of diameter $α$ centered at the points, with total area $19π\left(\frac α2\right)^2$. These circles all fit into the fundamental unit of this plane tiling with copies of the hexagon spaced $α$ apart:

which is a hexagon of side length $1 + \frac{α}{\sqrt 3}$ and area $k = \frac{3 \sqrt 3}{2}\left(1 + \frac{α}{\sqrt 3}\right)^2$. By Thue’s circle packing theorem, the total area of the circles must be at most $\frac{π}{2\sqrt 3}k$. This argument yields $α ≤ \frac{\sqrt 3}{\sqrt{19} - 1} \approx 0.51566$, and also suffices to bound the number of points at distance $\frac12$ to $19$ since $\frac{\sqrt 3}{\sqrt{20} - 1} \approx 0.49884$.

A stronger theorem from Folkman and Graham, “A packing inequality for compact subsets of the plane” (1969) gives the optimal bound:

If $A(X)$ and $P(X)$ denote the area and perimeter, respectively, of a compact convex subset $X$ of the plane, then $$\rho(X) \le \frac{2}{\sqrt 3}A(X) + \frac12P(X) + 1.$$

Here $\rho(X)$ is the size of the largest set of points in $X$ at mutual distance at least $1$. For a hexagon of side length $s$ containing $19$ points at distance at least $1$, we must have

$$19 \le \frac{2}{\sqrt 3} \cdot \frac{3 \sqrt{3}}{2}s^2 + \frac12 \cdot 6s + 1 = 3s^2 + 3s + 1,$$

whence $s \ge 2$. Scaling down by a factor of $s$ shows that $α ≤ \frac12$.