On lower bounds of the density of planar periodic sets without unit distances
Not on the map. Why?
Abstract (arXiv)
Determining the maximal density m1(ℝ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 m1(ℝ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 ≤ m1(ℝ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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 10 of its 26 references that are in the map. First posted on arXiv 20 Nov 2024.
Builds on
10 of 26 references.
References · 10
- 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
- 2017Proximal Policy Optimization Algorithmscited by 14,441
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
- 2020Learning What to Defer for Maximum Independent Setscited by 53
- 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 36
- 2015Finding Near-Optimal Independent Sets at Scalecited by 32
- 2018Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphscited by 9
- 2017Scalable Kernelization for Maximum Independent Setscited by 8
Built on by
Not cited yet.