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

$$H_3 = {\textstyle{1\over 2}}$$

$$H_4 = {\textstyle{1\over 2}}$$

$$H_5 = {\textstyle{1\over 9}}\sqrt{3}$$

$$H_6 = {\textstyle{1\over 8}}$$

$$H_7 \geq {\textstyle{1\over 12}}$$

$$H_8 \geq {\textstyle{1\over 4}}(2-\sqrt{3}\,)$$

$$H_9 \geq {\textstyle{1\over 21}}$$

$$H_{10} \geq {\textstyle{1\over 32}}(3\sqrt{17}-11)$$

$$H_{11} \geq {\textstyle{1\over 27}}$$

$$H_{12} \geq {\textstyle{1\over 33}}$$

$$H_{13} \geq 0.030$$

$$H_{14} \geq 0.022$$

$$H_{15} \geq 0.020$$

$$H_{16} \geq 0.0175.$$

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

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

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

Using an Equilateral Triangle of unit Area instead gives the constants

$$h_3 = 1$$

$$h_4 = {\textstyle{1\over 3}}$$

$$h_5 = 3-2\sqrt{2}$$

$$h_6 = {\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.