On diameter bounds for planar integral point sets in semi-general position
https://doi.org/10.22405/2226-8383-2021-22-4-344-351
Abstract
A point set 𝑀 in the Euclidean plane is said to be a planar integral point set if all the distances between the elements of 𝑀 are integers, and 𝑀 is not situated on a straight line.
A planar integral point set is said to be a set in semi-general position, if it does not contain collinear triples. The existing lower bound for mininal diameter of a planar integral point set is
linear with respect to its cardinality. There were no known special diameter bounds for planar integral point sets in semi-general position of given cardinality (the known upper bound for
planar integral point sets is constructive and employs planar integral point sets in semi-general position). We prove a new lower bound for minimal diameter of planar integral point sets in
semi-general position that is better than linear (polynomial of power 5/4). The proof is based on several lemmas and observations, including the ones established by Solymosi to prove the first linear lower bound for diameter of a planar integral point set.
References
1. Anning, N.H. & Erd¨os, P. 1945. “Integral distances”. Bulletin of the American Mathematical Society, vol. 51.8, pp. 598—600. doi: 10.1090/S0002-9904-1945-08407-9
2. Erd¨os, P. 1945. “Integral distances”. Bulletin of the American Mathematical Society, vol. 51.12, p. 996. doi: 10.1090/S0002-9904-1945-08490-0
3. Avdeev, N.N. & Semenov, E.M. 2018. “Mnozhestva tochek c tselochislennymi rasstoyaniyami na ploskosti i v evklidovom prostranstve” (“Integral point sets on the plane and in Euclidean
4. space”) Matematicheskiy forum (Itogi nauki. Yug Rossii), pp. 217—236.
5. Kurz, S. & Laue, R. 2007. “Bounds for the minimum diameter of integral point sets”. Australasian Journal of Combinatorics, vol. 39, pp. 233—240. arXiv: 0804.1296.
6. Kurz, S. & Wassermann, A. 2011. “On the minimum diameter of plane integral point sets”. Ars Combinatoria, vol. 101, pp. 265—287. arXiv: 0804.1307.
7. Antonov, A.R. & Kurz, S. 2008. “Maximal integral point sets over 𝑍2”. International Journal of Computer Mathematics, vol. 87.12, pp. 2653—2676. arXiv: 0804.1280. doi: 10.1080/
8.
9. Huff, G.B. 1948. “Diophantine problems in geometry and elliptic ternary forms”. Duke Mathematical Journal, vol. 15.2, pp. 443—453. doi:10.1215/S0012-7094-48-01543-9
10. Harborth, H., Kemnitz, A. & M¨oller, M. 1993. “An upper bound for the minimum diameter of integral point sets”. Discrete & Computational Geometry vol. 9.4, pp. 427—432. doi:
11. 1007/bf02189331
12. Piepmeyer, L. 1996. “The maximum number of odd integral distances between points in the plane”. Discrete & Computational Geometry, vol. 16.1, pp. 113—115. doi: 10.1007/bf02711135
13. Kreisel, T. & Kurz, S. 2008. “There are integral heptagons, no three points on a line, no four on a circle”. Discrete & Computational Geometry, vol. 39.4, pp. 786—790. doi: 10.1007/s00454-007-9038-6
14. Kurz, S., Noll, L.C., Rathbun, R, & Simmons, C. 2014. “Constructing 7-clusters”. Serdica Journal of Computing, vol. 8.1, pp. 47—70. arXiv: 1312.2318.
15. Solymosi, J. 2003. “Note on integral distances”. Discrete & Computational Geometry, vol. 30.2, pp. 337—342. doi: 10.1007/s00454-003-0014-7
16. Avdeev, N. N. 2019. “On existence of integral point sets and their diameter bounds”. Australasian Journal of Combinatorics, vol. 77.1, pp. 100—116. arXiv: 1906.11926
17. Bat-Ochir, G. 2018. “On the number of points with pairwise integral distances on a circle”. Discrete Applied Mathematics, vol. 254, pp. 17—32. doi: 10.1016/j.dam.2018.07.004
18. Brass, P., Moser, W.O.J. & Pach, J. 2006. Research problems in discrete geometry. Springer Science & Business Media. doi: 10.1007/0-387-29929-7
19. Guy, R. 2013. Unsolved problems in number theory. Vol. 1. Springer Science & Business Media. doi: 10.1007/978-1-4757-1738-9
20. Avdeev, N.N. 2018. “Ob otyskanii tseloudalennykh mnozhestv spetsial’nogo vida” (“On the search of integral point sets of a special type”). Aktual’nye problemy prikladnoj matematiki, informatiki i mekhaniki - sbornik trudov Mezhdunarodnoj nauchnoj konferencii. (Actual problems of applied mathematics, informatics and mechanics - proc. of the int. conf.). Voronezh, pp. 492—498.
21. Avdeev, N.N. 2018. “On integral point sets in special position”. Nekotorye voprosy analiza, algebry, geometrii i matematicheskogo obrazovaniya (Some problems of analysis, algebra, geometry and mathematical education), vol. 8, pp. 5—6.
22. Kurz, S. 2006. “On the characteristic of integral point sets in 𝐸𝑚”. Australasian Journal of Combinatorics, vol. 36, pp. 241–248. arXiv: math/0511704.
23. Nozaki, H. 2013. “Lower bounds for the minimum diameter of integral point sets”. Australasian Journal of Combinatorics, vol. 56, pp. 139—143.
24. Smurov, M. & Spivak, A. 1998. “Pokrytiya poloskami” (“Covering by strips”). Kvant, vol. 5, pp. 6–12.
Review
For citations:
Avdeev N.N. On diameter bounds for planar integral point sets in semi-general position. Chebyshevskii Sbornik. 2021;22(4):344-351. (In Russ.) https://doi.org/10.22405/2226-8383-2021-22-4-344-351
Views:
261
Email this article 