info prev up next book cdrom email home

Heilbronn Triangle Problem

N.B. A detailed on-line essay by S. Finch was the starting point for this entry.


Given any arrangement of $n$ points within a Unit Square, let $H_n$ be the smallest value for which there is at least one Triangle formed from three of the points with Area $\leq H_n$. The first few values are

$\displaystyle H_3$ $\textstyle =$ $\displaystyle {\textstyle{1\over 2}}$  
$\displaystyle H_4$ $\textstyle =$ $\displaystyle {\textstyle{1\over 2}}$  
$\displaystyle H_5$ $\textstyle =$ $\displaystyle {\textstyle{1\over 9}}\sqrt{3}$  
$\displaystyle H_6$ $\textstyle =$ $\displaystyle {\textstyle{1\over 8}}$  
$\displaystyle H_7$ $\textstyle \geq$ $\displaystyle {\textstyle{1\over 12}}$  
$\displaystyle H_8$ $\textstyle \geq$ $\displaystyle {\textstyle{1\over 4}}(2-\sqrt{3}\,)$  
$\displaystyle H_9$ $\textstyle \geq$ $\displaystyle {\textstyle{1\over 21}}$  
$\displaystyle H_{10}$ $\textstyle \geq$ $\displaystyle {\textstyle{1\over 32}}(3\sqrt{17}-11)$  
$\displaystyle H_{11}$ $\textstyle \geq$ $\displaystyle {\textstyle{1\over 27}}$  
$\displaystyle H_{12}$ $\textstyle \geq$ $\displaystyle {\textstyle{1\over 33}}$  
$\displaystyle H_{13}$ $\textstyle \geq$ $\displaystyle 0.030$  
$\displaystyle H_{14}$ $\textstyle \geq$ $\displaystyle 0.022$  
$\displaystyle H_{15}$ $\textstyle \geq$ $\displaystyle 0.020$  
$\displaystyle H_{16}$ $\textstyle \geq$ $\displaystyle 0.0175.$  

Komlós et al. (1981, 1982) have shown that there are constants $c$ such that

\begin{displaymath}
{c\ln n\over n^2}\leq H_n\leq {C\over n^{8/7}-\epsilon},
\end{displaymath}

for any $\epsilon>0$ and all sufficiently large $n$.


Using an Equilateral Triangle of unit Area instead gives the constants

$\displaystyle h_3$ $\textstyle =$ $\displaystyle 1$  
$\displaystyle h_4$ $\textstyle =$ $\displaystyle {\textstyle{1\over 3}}$  
$\displaystyle h_5$ $\textstyle =$ $\displaystyle 3-2\sqrt{2}$  
$\displaystyle h_6$ $\textstyle =$ $\displaystyle {\textstyle{1\over 8}}.$  


References

Finch, S. ``Favorite Mathematical Constants.'' http://www.mathsoft.com/asolve/constant/hlb/hlb.html

Goldberg, M. ``Maximizing the Smallest Triangle Made by $N$ Points in a Square.'' Math. Mag. 45, 135-144, 1972.

Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 242-244, 1994.

Komlos, J.; Pintz, J.; and Szemerédi, E. ``On Heilbronn's Triangle Problem.'' J. London Math. Soc. 24, 385-396, 1981.

Komlos, J.; Pintz, J.; and Szemerédi, E. ``A Lower Bound for Heilbronn's Triangle Problem.'' J. London Math. Soc. 25, 13-24, 1982.

Roth, K. F. ``Developments in Heilbronn's Triangle Problem.'' Adv. Math. 22, 364-385, 1976.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25