用图论方法重新评估平面上无单位距离点集的密度下界。
On lower bounds of the density of planar periodic sets without unit distances
- 将问题转化为平面上环面图的最大独立集求解。
- 实验表明现有下界0.22936未被突破，最优解逼近克罗夫特构造。
- 开源工具对比验证了方法可行性，适合组合几何研究者参考。
确定平面上无单位距离点集的最大密度 $m_1(bR^2)$ 是组合几何中的基础问题。本文通过将问题重构为基于平面环面构造的图上的最大独立集（MIS）问题，研究该量的下界。考虑相对于两个非共线向量的周期性点集，提出一种新方法。实验结果结合理论支持表明，在足够广泛的参数范围内，该方法未能改进已知下界 $0.22936 \le m_1(bR^2)$。找到的最佳离散点集近似于克罗夫特（Croft）的构造。同时，对多种用于求解MIS问题的开源软件包进行了比较。
原文摘要 · Abstract (English)
Determining the maximal density $m_1(\mathbb{R}^2)$ of planar sets without unit distances is a fundamental problem in combinatorial geometry. This paper investigates lower bounds for this quantity. We introduce a novel approach to estimating $m_1(\mathbb{R}^2)$ by reformulating the problem as a Maximal Independent Set (MIS) problem on graphs constructed from flat torus, focusing on periodic sets with respect to two non-collinear vectors. Our experimental results, supported by theoretical justifications of proposed method, demonstrate that for a sufficiently wide range of parameters this approach does not improve the known lower bound $0.22936 \le m_1(\mathbb{R}^2)$. The best discrete sets found are approximations of Croft's construction. In addition, several open source software packages for MIS problem are compared on this task.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。