×

Searching approximate global optimal Heilbronn configurations of nine points in the unit square via GPGPU computing. (English) Zbl 1372.90083

Summary: In this paper we present a method of applying the GPGPU technology to compute the approximate optimal solution to the Heilbronn problem for nine points in the unit square, namely, points \(P_1,P_2,\dots,P_9\) in \([0,1]\times [0,1]\) so that the minimal area of triangles \(P_iP_jP_k\) (\(1\leq i<j<k\leq 9\)) gets the maximal value \(h_9(\square )\). We construct nine rectangles with edge length 1/80 in the unit square which contain all optimal Heilbronn configurations up to possible rotation and reflection, and prove that \(\frac{9\sqrt{65}-55}{320}=0.054875999\cdots<h_9(\square )<0.054878314\), the lower bound here comes from F. Comellas and J. L. A. Yebra’s paper [Electron. J. Comb. 9, No. 1, Research paper R6, 10 p. (2002; Zbl 1008.52020)].

MSC:

90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C27 Combinatorial optimization

Citations:

Zbl 1008.52020

Software:

GloptiPoly
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brass, P., Moser, W., Pach, J.: Research Problems in Diecrete Geometry. Springer, New York (2005) · Zbl 1086.52001
[2] Komlós, J., Pintz, J., Szemerédi, E.: A lower bound for Heilbronn’s problem. J. Lond. Math. Soc. S2-25(1), 13-24 (1982) · Zbl 0483.52008
[3] Roth, K.F.: On a problem of Heilbronn. J. Lond. Math. Soc. S1-26(3), 198-204 (1951) · Zbl 0043.16303
[4] Komlós, J., Pintz, J., Szemerédi, E.: On Heilbronn’s triangle problem. J. Lond. Math. Soc. S2-24(3), 385-396 (1981) · Zbl 0483.52007
[5] Goldberg, M.: Maximizing the smallest triangle made by n points in a square. Math. Mag. 45(3), 135-144 (1972) · Zbl 0238.52006
[6] Yang, L., Zhang, J., Zeng, Z.: On goldbergs conjecture: computing the first several heilbronn numbers. Technical report 91-074, University Bielefeld (1991)
[7] Yang, L., Zhang, J., Zeng, Z.: A conjecture on the first several heilbronn numbers and a computation. Chin. Ann. Math. Ser. A 13, 503-515 (1992) · Zbl 0781.52004
[8] Dress, A.W.M., Yang, L., Zeng, Z.: Heilbronn problem for six points in a planar convex boxy. In: Du, D.-Z., Pardalos, P.M., (eds.) Minimax and Applications, pp. 173-190. Springer, US (1995) · Zbl 0879.52001
[9] Zeng, Z., Chen, L.: On the Heilbronn optimal configuration of seven points in the square. LNCS 6301, 196-224 (2011) · Zbl 1302.52022
[10] Chen, L., Zeng, Z., Zhou, W.: An upper bound of Heilbronn number for eight points in triangles. J. Comb. Optim. 28(4), 854-874 (2014). doi:10.1007/s10878-012-9585-5 · Zbl 1331.90063
[11] Comellas, F., Yebra, J.L.A.: New lower bounds for heilbronn numbers. Electr. J. Comb. 9(6), 1-10 (2002) · Zbl 1008.52020
[12] Audet, C., Hansen, P., Messine, F., Xiong, J.: The largest small octagon. J. Comb. Theory Ser. A. 98(1), 46-59 (2002) · Zbl 1022.90013
[13] Audet, C., Hansen, P., Messine, F., Perron, S.: The minimum diameter octagon with unit-length sides: Vincze’s wife’s octagon is suboptimal. J. Comb. Theory Ser. A. 108(1), 63-75 (2004) · Zbl 1107.90031
[14] Audet, C., Hansen, P., Messine, F.: The small octagon with longest perimeter. J. Comb. Theory Ser. A. 114(1), 135-150 (2007) · Zbl 1259.90096
[15] Henrion, D., Messine, F.: Finding largest small polygons with GloptiPoly. J. Glob. Optim. 56(3), 1017-1028 (2013) · Zbl 1272.90059
[16] Weisstein, E.W.: Heilbronn triangle problem. From MathWorld-a Wolfram Web resource. http://mathworld.wolfram.com/HeilbronnTriangleProblem.html. (2011) · Zbl 0812.52003
[17] Yang, L., Zhang, J., Zeng, Z.: On exact values of Heilbronn numbers for triangular regions. Technical report 91-098, University Bielefeld (1991)
[18] Yang, L., Zhang, J., Zeng, Z.: On the Heilbronn numbers of triangular regions. Acta Math. Sin. 37, 678-689 (1994) · Zbl 0812.52003
[19] Cantrell D.: The Heilbronn problem for triangles. http://www2.stetson.edu/ efriedma/heiltri/ (2011) · Zbl 1272.90059
[20] Comité, F D., Delahaye, J.: Automated proofs in geometry: computing upper bounds for the Heilbronn problem for triangles. http://arxiv.org/abs/0911.4375v3 (2009) · Zbl 1506.51014
[21] Comité, F.D., Delahaye, J.: A counterexample to Kahle-conjecture, new conjectures and automated proofs in geometry. http://www.lifl.fr/ decomite/triangle/triangles.html (2009) · Zbl 1022.90013
[22] Tal, A.: Algorithms for Heilbronn’s triangle problem. Msc thesis, Israel Institute of Technology, Haifa. http://ftp.cs.technion.ac.il/pub/barequet/theses/tal-a-msc-thesis.pdf.gz (2009)
[23] Owens, J., Luebke, D., Govindaraju, N., Harris, M.: A survey of general-purpose computation on graphics hardware. Comput. Graph. Forum 26(1), 80-113 (2007)
[24] Farber, R.: CUDA Application Design and Development. Morgan Kaufmann, Burlington (2011)
[25] Markót, M.C.: Optimal packing of 28 equal circles in a unit square—the first reliable solution. Numer. Algorithms 37(1), 253-261 (2004) · Zbl 1077.90056
[26] Kozikowski, K., Kubica, B.: Interval arithmetic and automatic differentiation on GPU using OpenCL. In: Manninen, P., Öster, P. (eds.), LNCS 7782, pp. 489-503 (2013) · Zbl 1022.90013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.