Heilbronn Triangle Problem

The Heilbronn triangle problem is to place points in a disk (square, equilateral triangle, etc.) of unit area so as to maximize the area of the smallest of the triangles determined by the points. For points, there is only a single triangle, so Heilbronn's problem degenerates into finding the largest triangle that can be constructed from points in a square. For , there are four possible triangles for each configuration, so the problem is to find the configuration of points for which the smallest of these four triangles is the maximum possible.

For a unit square, the first few maxima of minimal triangle areas are

			(1)
			(2)
			(3)
			(4)
			(5)
			(6)
			(7)
			(8)

For larger values of , proofs of optimality are open, but the best known results are

			(9)
			(10)
			(11)
			(12)
			(13)
			(14)
			(15)
			(16)
			(17)
			(18)
			(19)
			(20)
			(21)
			(22)
			(23)
			(24)
			(25)
			(26)
			(27)

with the configurations leading to maximum minimal triangles illustrated above (Friedman 2006; Comellas and Yebra 2002; D. Cantrell and M. Beyleveld, pers. comm., Aug.  16, 2006). Here, the notation indicates a polynomial root. As can be seen, the solutions have a great deal of symmetry, with a large number of maximum minimal triangles sharing the same area.

For disks with unit area, the Heilbronn configurations up to 7 are symmetric arrangements of points around the circumference. The best known Heilbronn constants for the circle are

			(28)
			(29)
			(30)
			(31)
			(32)
			(33)
			(34)
			(35)
			(36)
			(37)
			(38)
			(39)
			(40)
			(41)
			(42)
			(43)
			(44)
			(45)
			(46)
			(47)
			(48)
			(49)

(Friedman 2007; D. Cantrell pers. comm., Jun. 18, 2007).

Using an equilateral triangle of unit area instead gives the constants

			(50)
			(51)
			(52)
			(53)
			(54)
			(55)
			(56)
			(57)
			(58)
			(59)
			(60)
			(61)
			(62)
			(63)
			(64)
			(65)
			(66)
			(67)
			(68)
			(69)

(Friedman 2007; D. Cantrell, pers. comm., Jun. 18, 2007).

Heilbronn conjectured

(70)

but Komlós et al. (1981, 1982) disproved this by showing that

(71)

(Guy 1994, p. 243) and in particular that there are constants such that

(72)

for any and all sufficiently large . Roth (1951) then showed that

(73)

which Schmidt (1971/1972) improved to

(74)

and Roth further improved to

(75)

originally with (Roth 1972ab) and later with (Roth 1976; Guy 1994, p. 243). David Cantrell found a heuristic upper bound given by

(76)

Wolfram Web Resources