License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2023.32
URN: urn:nbn:de:0030-drops-178827
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17882/
Fernique, Thomas ;
Pchelina, Daria
When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques
Abstract
We consider ternary disc packings of the plane, i.e. the packings using discs of three different radii. Packings in which each "hole" is bounded by three pairwise tangent discs are called triangulated. Connelly conjectured that when such packings exist, one of them maximizes the proportion of the covered surface: this holds for unary and binary disc packings. For ternary packings, there are 164 pairs (r, s), 1 > r > s, allowing triangulated packings by discs of radii 1, r and s. In this paper, we enhance existing methods of dealing with maximal-density packings in order to study ternary triangulated packings. We prove that the conjecture holds for 31 triplets of disc radii and disprove it for 40 other triplets. Finally, we classify the remaining cases where our methods are not applicable. Our approach is based on the ideas present in the Hales' proof of the Kepler conjecture. Notably, our proof features local density redistribution based on computer search and interval arithmetic.
BibTeX - Entry
@InProceedings{fernique_et_al:LIPIcs.SoCG.2023.32,
author = {Fernique, Thomas and Pchelina, Daria},
title = {{When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques}},
booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)},
pages = {32:1--32:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-273-0},
ISSN = {1868-8969},
year = {2023},
volume = {258},
editor = {Chambers, Erin W. and Gudmundsson, Joachim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17882},
URN = {urn:nbn:de:0030-drops-178827},
doi = {10.4230/LIPIcs.SoCG.2023.32},
annote = {Keywords: Disc packing, density, interval arithmetic}
}
