Geodesic
On diameter bounds for planar integral point sets in semi-general position
Čebyševskij sbornik, Tome 22 (2021) no. 4, pp. 344-351.

Voir la notice de l'article provenant de la source Math-Net.Ru

A point set $M$ in the Euclidean plane is said to be a planar integral point set if all the distances between the elements of $M$ are integers, and $M$ 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.
Keywords: combinatorial geometry, diameter of a set, integral point set. 
@article{CHEB_2021_22_4_a18,
     author = {N. N. Avdeev},
     title = {On diameter bounds for planar integral point sets in semi-general position},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {344--351},
     publisher = {mathdoc},
     volume = {22},
     number = {4},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2021_22_4_a18/}
}
TY  - JOUR
AU  - N. N. Avdeev
TI  - On diameter bounds for planar integral point sets in semi-general position
JO  - Čebyševskij sbornik
PY  - 2021
SP  - 344
EP  - 351
VL  - 22
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2021_22_4_a18/
LA  - ru
ID  - CHEB_2021_22_4_a18
ER  - 
%0 Journal Article
%A N. N. Avdeev
%T On diameter bounds for planar integral point sets in semi-general position
%J Čebyševskij sbornik
%D 2021
%P 344-351
%V 22
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2021_22_4_a18/
%G ru
%F CHEB_2021_22_4_a18
N. N. Avdeev. On diameter bounds for planar integral point sets in semi-general position. Čebyševskij sbornik, Tome 22 (2021) no. 4, pp. 344-351. http://geodesic.mathdoc.fr/item/CHEB_2021_22_4_a18/

[1] Anning N. H., Erdos P., “Integral distances”, Bulletin of the American Mathematical Society, 51:8 (1945), 598-600 | DOI | MR | Zbl

[2] Erdos P., “Integral distances”, Bulletin of the American Mathematical Society, 51:12 (1945), 996 | DOI | MR

[3] Avdeev N. N., Semenov E. M., “Mnozhestva tochek s tselochislennymi rasstoyaniyami na ploskosti i v evklidovom prostranstve”, Matematicheskii forum (Itogi nauki. Yug Rossii), 2018, 217-236

[4] Kurz S., Laue R., “Bounds for the minimum diameter of integral point sets”, Australasian Journal of Combinatorics, 39 (2007), 233-240, arXiv: 0804.1296 | MR | Zbl

[5] Kurz S., Wassermann A., “On the minimum diameter of plane integral point sets”, Ars Combinatoria, 101 (2011), 265-287, arXiv: 0804.1307 | MR | Zbl

[6] Antonov A. R., Kurz S., “Maximal integral point sets over $\mathbb{Z}^2$”, International Journal of Computer Mathematics, 87:12 (2008), 2653-2676, arXiv: 0804.1280 | DOI | MR

[7] Huff G. B., “Diophantine problems in geometry and elliptic ternary forms”, Duke Mathematical Journal, 15:2 (1948), 443-453 | DOI | MR | Zbl

[8] Harborth H., Kemnitz A., Moller M., “An upper bound for the minimum diameter of integral point sets”, Discrete Computational Geometry, 9:4 (1993), 427-432 | DOI | MR | Zbl

[9] Piepmeyer L., “The maximum number of odd integral distances between points in the plane”, Discrete Computational Geometry, 16:1 (1996), 113-115 | DOI | MR | Zbl

[10] Kreisel T., Kurz S., “There are integral heptagons, no three points on a line, no four on a circle”, Discrete Computational Geometry, 39:4 (2008), 786-790 | DOI | MR | Zbl

[11] S. Kurz i dr., “Constructing 7-clusters”, Serdica Journal of Computing, 8:1 (2014), 47-70, arXiv: 1312.2318 | DOI | MR | Zbl

[12] Solymosi J., “Note on integral distances”, Discrete Computational Geometry, 30:2 (2003), 337-342 | DOI | MR | Zbl

[13] Avdeev N., “On existence of integral point sets and their diameter bounds”, Australasian Journal of Combinatorics, 77:1 (2020), 100-116, arXiv: 1906.11926 | MR | Zbl

[14] Bat-Ochir G., “On the number of points with pairwise integral distances on a circle”, Discrete Applied Mathematics, 254 (2018), 17-32 | DOI | MR

[15] Brass P., Moser W. O., Pach J., Research problems in discrete geometry, Springer Science Business Media, 2006 | MR

[16] Guy R., Unsolved problems in number theory, v. 1, Springer Science Business Media, 2013 | MR

[17] Avdeev N. N., “Ob otyskanii tseloudalennykh mnozhestv spetsialnogo vida”, Aktualnye problemy prikladnoi matematiki, informatiki i mekhaniki, sbornik trudov Mezhdunarodnoi nauchnoi konferentsii, Nauchno-issledovatelskie publikatsii, 2018, 492-498

[18] Avdeev N. N., “On integral point sets in special position”, materialy mezhdunarodnoi molodezhnoi nauchnoi shkoly «Aktualnye napravleniya matematicheskogo analiza i smezhnye voprosy», Nekotorye voprosy analiza, algebry, geometrii i matematicheskogo obrazovaniya, 8, 2018, 5–6

[19] Kurz S., “On the characteristic of integral point sets in $E^m$”, Australasian Journal of Combinatorics, 36 (2006), 241, arXiv: math/0511704 | MR | Zbl

[20] Nozaki H., “Lower bounds for the minimum diameter of integral point sets”, Australasian Journal of Combinatorics, 56 (2013), 139-143 | MR | Zbl

[21] Smurov M., Spivak A., “Pokrytiya poloskami”, Kvant, 1998, no. 5, 6