License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.48
URN: urn:nbn:de:0030-drops-122064
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12206/
Go to the corresponding LIPIcs Volume Portal

Frankl, Nóra ; Kupavskii, Andrey

Almost Sharp Bounds on the Number of Discrete Chains in the Plane

pdf-format:
LIPIcs-SoCG-2020-48.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{frankl_et_al:LIPIcs:2020:12206,
  author =	{N{\'o}ra Frankl and Andrey Kupavskii},
  title =	{{Almost Sharp Bounds on the Number of Discrete Chains in the Plane}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12206},
  URN =		{urn:nbn:de:0030-drops-122064},
  doi =		{10.4230/LIPIcs.SoCG.2020.48},
  annote =	{Keywords: unit distance problem, unit distance graphs, discrete chains}
}

Keywords: unit distance problem, unit distance graphs, discrete chains
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI