Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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
3  
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 1

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/

share|improve this answer
    
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

Your Answer

 
discard

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.