Heilbronn's Problem of Eight Points in the Square

doi:10.1007/s11424-022-1220-7

Journal of Systems Science and Complexity ›› 2022, Vol. 35 ›› Issue (6): 2452-2480.DOI: 10.1007/s11424-022-1220-7

Heilbronn's Problem of Eight Points in the Square

DEHBI Lydia^1,2, ZENG Zhenbing²

1. School of Software Engineering, East China Normal University, Shanghai 200062, China;
2. Department of Mathematics, Shanghai University, Shanghai 200444, China

Received:2021-06-25 Revised:2021-10-26 Online:2022-11-25 Published:2022-12-23
Contact: ZENG Zhenbing,Email:zbzeng@shu.edu.cn
Supported by:
This research was supported by the National Natural Science Foundation of China under Grant Nos. 12171159 and 12071282, and "Digital Silk Road" Shanghai International Joint Lab of Trustworthy Intelligent Software under Grant No. 22510750100.

PDF ( 2 ) Cited

DEHBI Lydia, ZENG Zhenbing. Heilbronn's Problem of Eight Points in the Square[J]. Journal of Systems Science and Complexity, 2022, 35(6): 2452-2480.

In this work the authors consider the problem of optimally distributing 8 points inside a unit square so that the smallest area of the ${8\choose 3}$ triangles formed by them is maximal. Symbolic computations are employed to reduce the problem into a nonlinear programming problem and find its optimal solution. All computations are done using Maple.

Key words: Global search, Heilbronn's problem, optimal configuration, smallest triangle's area, symbolic computations

[1] Brass P, Moser W, and Pach J, Research Problems in Discrete Geometry, Springer Science & Business Media, Berlin, 2006.
[2] Bertram-Kretzberg C, Hofmeister T, and Lefmann H, An algorithm for Heilbronn’s problem, SIAM Journal on Computing, 2000, 30(2): 383–390.
[3] Roth K, On a problem of Heilbronn, Journal of the London Mathematical Society, 1951, 1(3): 198–204.
[4] Roth K, On a problem of Heilbronn, ii, Proceedings of the London Mathematical Society, 1972, 3(2): 193–212.
[5] Roth K, On a problem of Heilbronn, iii, Proceedings of the London Mathematical Society, 1972, 3(3): 543–549.
[6] Schmidt W, On a problem of Heilbronn, Journal of the London Mathematical Society, 1972, 2(3): 545–550.
[7] Komlós J, Pintz J, and Szemerédi E, On Heilbronn’s triangle problem, Journal of the London Mathematical Society, 1981, 2(3): 385–396.
[8] Komlós J, Pintz J, and Szemerédi E, A lower bound for Heilbronn’s problem, Journal of the London Mathematical Society, 1982, 2(1): 13–24.
[9] Roth K, Developments in Heilbronn’s triangle problem, Advances in Mathematics, 1976, 22(3): 364–385.
[10] Goldberg M, Maximizing the smallest triangle made by n points in a square, Mathematics Magazine, 1972, 45(3): 135–144.
[11] Comellas F and Yebra J, New lower bounds for Heilbronn numbers, The Electronic Journal of Combinatorics, 2002, R6.
[12] Friedman E, The Heilbronn problem for squares, Accessed on October 15, 2022, https://erichfriedman.github.io/packing/heilbronn/.
[13] Tal A and Barequet G, Algorithms for Heilbronn’s triangle problem, PhD thesis, Computer Science Department, Technion, 2009.
[14] Yang L, Zhang J, and Zeng Z, Heilbronn problem for five points, Technical report, International Centre for Theoretical Physics, 1991.
[15] Yang L, Zhang J, and Zeng Z, On goldbergs conjecture: Computing the first several Heilbronn numbers, Technical report, Universitat Bielefeld, 1991.
[16] Yang L, Zhang J, and Zeng Z, On the conjecture and computing for exact values of the first several Heilbronn numbers, Chin. Ann. Math. (A), 1992, 13(4): 503–515.
[17] Zeng Z and Chen L, On the Heilbronn optimal configuration of seven points in the square, International Workshop on Automated Deduction in Geometry, Springer, 2008, 196–224.
[18] Barequet G, A lower bound for Heilbronn’s triangle problem in d dimensions, SIAM Journal on Discrete Mathematics, 2001, 14(2): 230–236.
[19] Barequet G, The on-line Heilbronn’s triangle problem, Discrete Mathematics, 2004, 283(1–3): 7–14.
[20] Barequet G and Shaikhet A, The on-line Heilbronn’s triangle problem in d dimensions, Discrete & Computational Geometry, 2007, 38(1): 51–60.
[21] Jiang T, Li M, and Vitányi P, The average-case area of Heilbronn-type triangles, Random Structures & Algorithms, 2002, 20(2): 206–219.
[22] Yang L, Zhang J, and Zeng Z, On the first several Heilbronn numbers of a triangle, Acta Mathematica Sinica, Chinese Series, 1994, 37(5): 678–689.

No related articles found!

Viewed

Full text

Abstract