首页    期刊浏览 2024年12月03日 星期二
登录注册

文章基本信息

  • 标题:Almost Sharp Bounds on the Number of Discrete Chains in the Plane
  • 本地全文:下载
  • 作者:N{'o}ra Frankl ; Andrey Kupavskii
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2020
  • 卷号:164
  • 页码:48:1-48:15
  • DOI:10.4230/LIPIcs.SoCG.2020.48
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:unit distance problem; unit distance graphs; discrete chains
国家哲学社会科学文献中心版权所有