DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2023.32

When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques

Authors: Thomas Fernique and Daria Pchelina

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

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.

Cite as

Thomas Fernique and Daria Pchelina. When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.SoCG.2023.32},
  URN =		{urn:nbn:de:0030-drops-178827},
  doi =		{10.4230/LIPIcs.SoCG.2023.32},
  annote =	{Keywords: Disc packing, density, interval arithmetic}
}

Search Results

Documents authored by Fernique, Thomas

When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques

Abstract

Cite as

Thanks for your feedback!

Could not send message