TOPICS
Search

Heilbronn Triangle Problem


The Heilbronn triangle problem is to place n>=3 points in a disk (square, equilateral triangle, etc.) of unit area so as to maximize the area Delta(n) of the smallest of the (n; 3)=n(n-1)(n-2)/6 triangles determined by the n points. For n=3 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 n=4, 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.

HeilbronnSquares

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

H_3=1/2
(1)
=0.5
(2)
H_4=1/2
(3)
=0.5
(4)
H_5=1/9sqrt(3)
(5)
=0.1924...
(6)
H_6=1/8
(7)
=0.125.
(8)

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

H_7>=(1-14x+12x^2+152x^3)_2
(9)
=0.083859...
(10)
H_8>=((sqrt(13)-1))/(36)
(11)
=0.072376...
(12)
H_9>=((9sqrt(65)-55))/(320)
(13)
=0.054876...
(14)
H_(10)>=(-9+268x-1764x^2+3456x^3)_1
(15)
=0.046537...
(16)
H_(11)>=1/(27)
(17)
=0.037037...
(18)
H_(12)>=(-1+28x+80x^2+64x^3)_1
(19)
=0.032599...
(20)
H_(13)>=0.026697431807596567
(21)
H_(14)>=(1-60x+768x^2+320x^3)_2
(22)
=0.024304...
(23)
H_(15)>=(29)/(1395)
(24)
=0.020789...
(25)
H_(16)>=7/(341)
(26)
=0.020528...,
(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 (P(x))_n 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.

HeilbronnDisks

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

H_3=(3sqrt(3))/(4pi)
(28)
=0.413497...
(29)
H_4=1/pi
(30)
=0.318310...
(31)
H_5=(sqrt(5/3(5-sqrt(5))))/(4pi)
(32)
=0.209182...
(33)
H_6=(sqrt(3))/(4pi)
(34)
=0.137832...
(35)
H_7>=((-343+294x^2-35x^4+x^6)_4)/(4pi)
(36)
=0.093700...
(37)
H_8>=((-7+14x^2-7x^4+x^6)_4)/(4pi)
(38)
=0.069055...
(39)
H_9>=0.05531071895608711
(40)
H_(10)>=((-27+81x^2-18x^4+x^6)_4)/(4pi)
(41)
=0.047869...
(42)
H_(11)>=0.03494193340280051
(43)
H_(12)>=0.03339560352492413
(44)
H_(13)>=0.02726586326658908
(45)
H_(14)>=0.02414611295141071
(46)
H_(15)>=0.02229427231706078
(47)
H_(16)>=((-9+103x+452x^2+476x^3+3776x^4+976x^5)_3)/pi
(48)
=0.021051...
(49)

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

HeilbronnTriangles

Using an equilateral triangle of unit area instead gives the constants

H_3=1
(50)
H_4=1/3
(51)
=0.3333...
(52)
H_5=3-2sqrt(2)
(53)
=0.1715...
(54)
H_6=1/8
(55)
=0.137832...
(56)
H_7>=7/(72)
(57)
=0.097222...
(58)
H_8>=0.06778914101959856
(59)
=0.067789...
(60)
H_9>=(43)/(784)
(61)
=0.054847...
(62)
H_(10)>=0.04337673349889024
(63)
H_(11)>=0.03609267801015405
(64)
H_(12)>=0.03100478174352528
(65)
H_(13)>=0.02456425934867466
(66)
H_(14)>=0.02377577301721215
(67)
H_(15)>=0.02109025290939601
(68)
H_(16)>=0.01797627598723551
(69)

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

Heilbronn conjectured

 Delta(n)<c/(n^2),
(70)

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

 Delta(n)>(lnn)/(n^2)
(71)

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

 (clnn)/(n^2)<=H_n<=C/(n^(8/7-epsilon))
(72)

for any epsilon>0 and all sufficiently large n. Roth (1951) then showed that

 Delta(n)<<1/(n(lnlnn)^(1/2)),
(73)

which Schmidt (1971/1972) improved to

 Delta(n)<<1/(n(lnn)^(1/2)),
(74)

and Roth further improved to

 Delta(n)<<1/(n^mu-epsilon),
(75)

originally with mu=2-2/sqrt(5)>1.1055 (Roth 1972ab) and later with mu=(17-sqrt(65))/8>1.1172 (Roth 1976; Guy 1994, p. 243). David Cantrell found a heuristic upper bound given by

 Delta(n)<(3logn-2+3)/(3n^2-14n+18).
(76)

See also

Disk Point Picking, Disk Triangle Picking, Square Point Picking, Square Triangle Picking, Triangle Point Picking, Triangle Triangle Picking

Explore with Wolfram|Alpha

References

Comellas, F. and Yebra, J. L. A. "New Lower Bounds for Heilbronn Numbers." Elec. J. Comb. 9, 2002. http://www.combinatorics.org/Volume_9/PDF/v9i1r6.pdf.Finch, S. R. Mathematical Constants. Cambridge, England: Cambridge University Press, 2003.Friedman, E. "The Heilbronn Problem." http://www.stetson.edu/~efriedma/heilbronn/.Friedman, E. "The Heilbronn Problem for Circles." http://www.stetson.edu/~efriedma/heilcirc/.Friedman, E. "The Heilbronn Problem for Squares." http://www.stetson.edu/~efriedma/heilbronn/.Friedman, E. "The Heilbronn Problem for Triangles." http://www.stetson.edu/~efriedma/heiltri/.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. 243-244, 1994.Jiang, T.; Li, M.; and Vitányi, P. "The Average-Case Area of Heilbronn-Type Triangle." Random Structures and Algorithms 20, 206-219, 2002.Komlós, J.; Pintz, J.; and Szemerédi, E. "On Heilbronn's Triangle Problem." J. London Math. Soc. 24, 385-396, 1981.Komlós, 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. "On a Problem of Heilbronn." J. London Math. Soc. 26, 198-204, 1951.Roth, K. F. "On a Problem of Heilbronn. II." Proc. London Math. Soc. 25, 193-212, 1972a.Roth, K. F. "On a Problem of Heilbronn. III." Proc. London Math. Soc. 25, 543-549, 1972b.Roth, K. F. "Developments in Heilbronn's Triangle Problem." Adv. Math. 22, 364-385, 1976.Schmidt, W. "On a Problem of Heilbronn." J. London Math. Soc. 4, 545-550, 1971/1972.

Referenced on Wolfram|Alpha

Heilbronn Triangle Problem

Cite this as:

Weisstein, Eric W. "Heilbronn Triangle Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HeilbronnTriangleProblem.html

Subject classifications