14
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Gjergji Zaimi
    Commented Mar 10, 2011 at 6:52
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Gjergji Zaimi
    Commented Mar 10, 2011 at 7:18
  • $\begingroup$ 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. $\endgroup$
    – Christian Elsholtz
    Commented Mar 10, 2011 at 7:49
  • $\begingroup$ Loosely related problem. en.wikipedia.org/wiki/Random_geometric_graph $\endgroup$
    – Tony Huynh
    Commented Mar 10, 2011 at 13:06

1 Answer 1

Reset to default
5
$\begingroup$

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 https://erich-friedman.github.io/packing/cirintri/ and https://erich-friedman.github.io/packing/circovtri/

Since the Heilbronn triangle problem has been mentioned, that has data at https://erich-friedman.github.io/packing/heiltri/

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Commented Mar 11, 2011 at 3:29
  • $\begingroup$ @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. $\endgroup$
    – Gerry Myerson
    Commented Mar 11, 2011 at 4:47

You must log in to answer this question.

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