# On lower bounds of the density of planar periodic sets without unit distances

arXiv: https://arxiv.org/abs/2411.13248 · HTML: https://mlsanity.com/paper/2411.13248/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 20 Nov 2024.

## Builds on (most cited first, 10 of 10)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs](https://mlsanity.com/paper/1810.10834/) (2018)
- [Scalable Kernelization for Maximum Independent Sets](https://mlsanity.com/paper/1708.06151/) (2017)

## 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.