Algorithms for computing iso-Delaunay domains

Contributed by Mathieu Dutour Sikiric ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

For a linear space TT of quadratic forms, we describe an algorithm enumerating the iso-Delaunay domains of TT, and a randomized search for an iso-Delaunay domain all of whose extreme rays are positive definite. For the quadratic forms in six variables, the search finds 14721472 pairwise inequivalent LL-type domains all of whose extreme rays are positive definite, the smallest having 2424 facets and 4747 extreme rays. No such domain exists in dimension 2≤n≤52\leq n\leq 5.

Author comments: 17 pages. The algorithms are implemented in polyhedral_common, https://github.com/MathieuDutSik/polyhedral_common. The data of the 1472 domains are at https://doi.org/10.5281/zenodo.24377749

Provenance statement

Text declaration: A mix of human-written and AI-generated.

Tools used

Anthropic
Claude Opus 5.5 (via Claude Code)

References

  1. Leiden declaration on artificial intelligence and mathematics, June 2026. Endorsed by the International Mathematical Union. https://leidendeclaration.ai/.link
  2. David Avis and Komei Fukuda. A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete & Computational Geometry , 8:295--313, 1992.
  3. Igor A. Baburin and Peter Engel. On the enumeration of the combinatorial types of primitive parallelohedra in EdE^d , 2≤d≤62 \leq d \leq 6. Acta Crystallographica Section A: Foundations of Crystallography , 69(5):510--516, 2013.
  4. David Bremner, Komei Fukuda, and Ambros Marzetta. Primal-dual methods for vertex and facet enumeration. Discrete & Computational Geometry , 20:333--357, 1998.
  5. Winfried Bruns and Bogdan Ichim. Normaliz: algorithms for affine monoids and rational cones. Journal of Algebra , 324(5):1098--1113, 2010.
  6. Kenneth L. Clarkson. More output-sensitive geometric algorithms. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science , pages 695--702. IEEE Computer Society, 1994.
  7. Michel Deza and Monique Laurent. Geometry of Cuts and Metrics , volume 15 of Algorithms and Combinatorics . Springer, Berlin, 1997.
  8. Mathieu Dutour and Frank Vallentin. Some six-dimensional rigid forms. In H. Syta, A. Yurachivsky, and P. Engel, editors, Voronoi's Impact on Modern Science, Book 3 , volume 55 of Proceedings of the Institute of Mathematics of the National Academy of Sciences of Ukraine , pages 102--108. Kiev, 2005. Preprint at https://arxiv.org/abs/math/0401191.link
  9. Mathieu Dutour Sikiri ć . polyhedral, a GAP package. https://github.com/MathieuDutSik/GAPpackages.link
  10. Mathieu Dutour Sikiri ć . Polytopes, lattices and quadratic forms programs. GitHub repository. Version of 19 November 2026, https://github.com/MathieuDutSik/polyhedral_common.link
Show all 24 referencesShow fewer references
  1. Mathieu Dutour Sikiri ć . The Birkhoff polytope of the groups F4F_4 and H4H_4 . In Tomislav Do š li ć , Snje ž ana Majstorovi ć , and Luka Podrug, editors, Proceedings of the 4th Croatian Combinatorial Days , pages 21--26, 2023. Preprint at https://arxiv.org/abs/2212.08452.link
  2. Mathieu Dutour Sikiri ć . List of G ram matrices in the interior of iso- D elaunay of rank 6 whose extreme rays are of full rank. Zenodo, 2026. https://doi.org/10.5281/zenodo.24377749.DOI
  3. Mathieu Dutour Sikiri ć , Herbert Gangl, Paul E. Gunnells, Jonathan Hanke, Achill Sch ü rmann, and Dan Yasaki. On the cohomology of linear groups over imaginary quadratic fields. Journal of Pure and Applied Algebra , 220(7):2564--2589, 2016.
  4. Mathieu Dutour Sikiri ć , Alexey Garber, Achill Sch ü rmann, and Clara Waldmann. The complete classification of five-dimensional Dirichlet--Voronoi polyhedra of translational lattices. Acta Crystallographica Section A: Foundations and Advances , 72(6):673--683, 2016.
  5. Mathieu Dutour Sikiri ć and Viatcheslav Grishukhin. How to compute the rank of a Delaunay polytope. European Journal of Combinatorics , 28(3):762--773, 2007. https://arxiv.org/abs/math/0512193.link
  6. Mathieu Dutour Sikiri ć , Achill Sch ü rmann, and Frank Vallentin. A generalization of Voronoi 's reduction theory and its application. Duke Mathematical Journal , 142(1):127--164, 2008.
  7. Michael Joswig. Beneath-and-beyond revisited. In Michael Joswig and Nobuki Takayama, editors, Algebra, Geometry, and Software Systems , pages 1--21. Springer, 2003.
  8. Sebastian Miebach. Sphere coverings of E isenstein, G aussian and H urwitzian lattices. Master's thesis, University of Cologne, 2025. Master's thesis, supervised by Frank Vallentin.
  9. Theodore S. Motzkin, Howard Raiffa, Gerald L. Thompson, and Robert M. Thrall. The double description method. In Contributions to the Theory of Games II , volume 28 of Annals of Mathematics Studies , pages 51--73. Princeton University Press, 1953.
  10. Wilhelm Plesken and Bernd Souvignier. Computing isometries of lattices. Journal of Symbolic Computation , 24(3--4):327--334, 1997.
  11. Achill Sch ü rmann. Enumerating perfect forms. In Quadratic Forms---Algebra, Arithmetic, and Geometry , volume 493 of Contemporary Mathematics , pages 359--377. American Mathematical Society, Providence, RI, 2009. https://arxiv.org/abs/0901.1587.link
  12. Achill Sch ü rmann and Frank Vallentin. scc (secondary cone cruiser). Computer program.
  13. Frank Vallentin. Sphere Coverings, Lattices, and Tilings (in Low Dimensions) . PhD thesis, Technische Universit ä t M ü nchen, 2003. https://mediatum.ub.tum.de/doc/602017/file.pdf.link
  14. Georges Vorono ï . Nouvelles applications des param è tres continus à la th é orie des formes quadratiques. deuxi è me m é moire: Recherches sur les parall é lo è dres primitifs. Journal f ü r die reine und angewandte Mathematik , 134:198--287, 1908.

Version history

  1. v1 · 17 pagesSubmitted by Mathieu Dutour Sikiric17 pages. The algorithms are implemented in polyhedral_common, https://github.com/MathieuDutSik/polyhedral_common. The data of the 1472 domains are at https://doi.org/10.5281/zenodo.24377749CurrentNov 19, 2026