2026-07-21T12:35:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12206 2024-03-06T10:49:42Z ddc:004 open_access

Almost Sharp Bounds on the Number of Discrete Chains in the Plane Frankl, Nóra Kupavskii, Andrey unit distance problem unit distance graphs discrete chains The following generalisation of the Erdős unit distance problem was recently suggested by Palsson, Senger and Sheffer. For a sequence δ=(δ₁,… ,δ_k) of k distances, a (k+1)-tuple (p₁,… ,p_{k+1}) of distinct points in ℝ^d is called a (k,δ)-chain if ‖p_j-p_{j+1}‖ = δ_j for every 1 ≤ j ≤ k. What is the maximum number C_k^d(n) of (k,δ)-chains in a set of n points in ℝ^d, where the maximum is taken over all δ? Improving the results of Palsson, Senger and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k ≡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nóra Frankl and Andrey Kupavskii 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.48 urn:nbn:de:0030-drops-122064 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.48 eng https://creativecommons.org/licenses/by/3.0/legalcode