# Put as many points as possible in an equilateral triangle of side 1 with their minimal distance greater than 1/n

It is known by the pigeon-hole principle that:

1. If we select $5$ points within an equilateral triangle with side $1$, there must be at least two whose distance apart is less than or equal to $1/2$.
2. And if we select $10$ points, there must be at least two whose distance apart is $\leq 1/3$.
3. Generally, if we select $n^2+1$ points, there must be at least two with distance $\leq 1/n$.

But $n^2+1$ seems not to be a tight bound. My question is:

To determine a minimum integer $m(n)$ such that if we select $m(n)$ points within an equilateral triangle with side $1$, there must be at least two points having distance $\leq 1/n$.

Equivalently,

To determine the maximum integer $m(n)$ satisfying that there exists a configuration of $m(n)-1$ points within an equilateral triangle with side $1$ such that the minimal distance among these points is greater than $1/n$.

It is clear that $m(1)=2$ and $m(2)=5$, both matching $n^2+1$. But a roughly pencil-and-paper work shows that $m(3)$ is not $10$ anymore.

Note: points can be located on the three sides of the triangle.

• I can't think of a way to find the exact form of $m(n)$ yet. but it is already interesting to ask what is $\lim m(n)/n^2$? – Gjergji Zaimi Mar 10 '11 at 6:52
• One way to observe that $\lim m(n)/n^2 \le 5/6$ is that inside a regular hexagon of edge $a$ there are at most 5 points at distance $>a$ from each other. On the other hand an easy observation is that $m(n)\geq n(n-1)/2$. – Gjergji Zaimi Mar 10 '11 at 7:18
• The Heilbronn triangle problem asks a similar question about areas, rather than distances. mathworld.wolfram.com/HeilbronnTriangleProblem.html What is the maximum (taken over all configurations of $n$ points in the in the unit equilateral triangle) of the minimum area of all $\binom{n}{3}$ triangles. Heilbronn conjectured the order of magnitude is $\ll 1/n^2$, which was disproved. – Christian Elsholtz Mar 10 '11 at 7:49
• Loosely related problem. en.wikipedia.org/wiki/Random_geometric_graph – Tony Huynh Mar 10 '11 at 13:06

## 1 Answer

This is related to problems of packing circles into an equilateral triangle, and covering an equilateral triangle by circles. Some data on these problems is available at http://www2.stetson.edu/~efriedma/cirintri/ and http://www2.stetson.edu/~efriedma/circovtri/

Since the Heilbronn triangle problem has been mentioned, that has data at http://www2.stetson.edu/~efriedma/heiltri/

• But here the problem is slightly different. It seems related to "loose" packings and coverings, that is packings with no circles tangent to each other and coverings with open disks. – Gjergji Zaimi Mar 11 '11 at 3:29
• @Gjergji, packings yield lower bounds for $m(n)$, but they don't seem to give anything better than the $n(n-1)/2$ you mention in a comment. I thought coverings would give upper bounds, but I don't see how to get anything useful out. – Gerry Myerson Mar 11 '11 at 4:47