An algorithmic approach for computing fundamental domains of crystallographic groups
Pith reviewed 2026-07-03 02:06 UTC · model grok-4.3
The pith
The half-spaces defining Dirichlet cells of crystallographic groups come from group elements expressible as words of bounded length in a generating set.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The half-spaces defining such a Dirichlet cell can be derived from elements of Γ acting on R^n that can be expressed as words of bounded length in a suitable generating set. Based on these results, an algorithm for the computation of fundamental domains of crystallographic groups is designed and used to study topological interlocking assemblies.
What carries the argument
Elements of the crystallographic group expressed as words of bounded length whose isometries determine the half-spaces of the Dirichlet cell.
If this is right
- Only finitely many words need to be checked to obtain all half-spaces of the Dirichlet cell.
- Fundamental domains become computable for every crystallographic group despite the group being infinite.
- The resulting cells can be used directly as fundamental domains in geometric constructions.
- The algorithm supplies explicit domains for the study of topological interlocking assemblies.
Where Pith is reading between the lines
- If an explicit method to compute the bound from the generating set is found, the algorithm becomes fully automatic.
- Similar length bounds might make fundamental domains computable for other discrete groups acting on Euclidean space.
- Software built on the algorithm could generate large families of interlocking structures for materials or architectural design.
Load-bearing premise
There exists a finite bound on word length such that every half-space of the Dirichlet cell is produced by some element whose word representation is at most that long.
What would settle it
An explicit crystallographic group together with a generating set for which at least one bounding half-space of its Dirichlet cell requires a group element whose shortest word representation exceeds every finite candidate bound.
Figures
read the original abstract
A crystallographic group is a discrete subgroup of the Euclidean group $\operatorname{E}(n)$ that has a compact fundamental domain. Since such a crystallographic group $\Gamma$ is infinite, computing fundamental domains of $\Gamma$ is algorithmically challenging. We address this difficulty by targeting the computation of Dirichlet cells that can form fundamental domains of $\Gamma$. We show that the half-spaces defining such a Dirichlet cell can be derived from elements of $\Gamma$ acting on $\mathbb{R}^n$ that can be expressed as words of bounded length in a suitable generating set. Based on these results, we design an algorithm for the computation of fundamental domains of crystallographic groups and exploit it to study the construction of topological interlocking assemblies.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript asserts that for a crystallographic group Γ ≤ E(n), the half-spaces defining a Dirichlet fundamental domain arise from group elements expressible as words of bounded length in a suitable generating set; it uses this to design an algorithm for computing such domains and applies the algorithm to examples in topological interlocking assemblies.
Significance. A fully effective version of the claimed algorithm would supply a practical computational tool for enumerating fundamental domains of infinite discrete subgroups of the Euclidean group, where naive orbit enumeration is impossible; this would be a concrete advance in computational crystallography and geometric group theory.
major comments (2)
- [Abstract] Abstract: the central claim that 'words of bounded length' suffice for all relevant half-spaces is asserted on the basis of discreteness of the orbit, but the manuscript supplies neither an explicit computable upper bound on that length (in terms of the input generators) nor an independent termination test; without one of these the algorithm is not shown to be effective for arbitrary input data.
- [Algorithm description] Algorithm section: the termination argument for the enumeration procedure is load-bearing for the main result, yet the text does not demonstrate that the procedure halts after finitely many steps when only the generators are given; this gap prevents verification that the method is fully algorithmic.
minor comments (1)
- The notation for the generating set S and the word-length function should be introduced with explicit definitions before the statement of the main theorem.
Simulated Author's Rebuttal
We thank the referee for the thorough review and for identifying the key points where the effectiveness of the algorithm requires further justification. We address each major comment below and will revise the manuscript to strengthen the presentation of the algorithmic claims.
read point-by-point responses
-
Referee: [Abstract] Abstract: the central claim that 'words of bounded length' suffice for all relevant half-spaces is asserted on the basis of discreteness of the orbit, but the manuscript supplies neither an explicit computable upper bound on that length (in terms of the input generators) nor an independent termination test; without one of these the algorithm is not shown to be effective for arbitrary input data.
Authors: The manuscript establishes the existence of a finite bound on word length via the discreteness of the orbit and compactness of any fundamental domain, which guarantees that only finitely many half-spaces are needed. However, the proof does not yield an explicit, computable expression for this bound directly from the input generators, nor does it supply an independent termination test. We agree that this leaves the algorithm short of being fully effective for arbitrary input data. In the revision we will add an explicit discussion of this limitation in both the abstract and the theoretical section, together with practical heuristics used in the examples. revision: yes
-
Referee: [Algorithm description] Algorithm section: the termination argument for the enumeration procedure is load-bearing for the main result, yet the text does not demonstrate that the procedure halts after finitely many steps when only the generators are given; this gap prevents verification that the method is fully algorithmic.
Authors: The termination of the enumeration is intended to follow from the finite bound whose existence is proved earlier. As the referee correctly observes, the current text does not demonstrate that this bound is computable from the generators alone, so the procedure is not shown to halt after finitely many steps for arbitrary input. We will revise the algorithm section to state the precise conditions under which termination is guaranteed, to separate the existence result from the question of computability, and to indicate where additional geometric tests (e.g., checking that all orbit points beyond a certain radius lie outside the current cell) could serve as a practical stopping criterion. revision: yes
Circularity Check
No circularity: derivation rests on group discreteness and finiteness, not self-reference or fitted inputs.
full rationale
The abstract states that half-spaces derive from group elements of bounded word length in a generating set, but supplies no equations, fitted parameters, or self-citations that reduce the claim to its own inputs by construction. Discreteness of crystallographic groups guarantees finitely many relevant elements, so existence of some bound follows from standard facts about discrete subgroups of E(n) without requiring the paper to presuppose the algorithm's output. No load-bearing step matches any enumerated circularity pattern; the result is self-contained against external group-theoretic benchmarks.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption Crystallographic groups are discrete subgroups of E(n) with compact fundamental domains (standard definition).
- domain assumption Dirichlet cells can serve as fundamental domains for such groups.
Reference graph
Works this paper leans on
-
[1]
Abeille.Machines et inventions approuvées par l’Académie Royale des Sciences depuis son étab- lissement jusqu’à present; avec leur Description
J. Abeille.Machines et inventions approuvées par l’Académie Royale des Sciences depuis son étab- lissement jusqu’à present; avec leur Description. Académie royale des Sciences, 1735. 13
-
[2]
Über die Bewegungsgruppen der euklidischen Räume. (Zweite Abhandlung.) Die Gruppen mit einem endlichen Fundamentalbereich
L. Bieberbach. “Über die Bewegungsgruppen der euklidischen Räume. (Zweite Abhandlung.) Die Gruppen mit einem endlichen Fundamentalbereich.” German. In:Math. Ann.72 (1912), pp. 400– 412
1912
-
[3]
Brown, R
H. Brown, R. Bülow, J. Neubüser, H. Wondratschek, and H. Zassenhaus.Crystallographic groups of four-dimensional space. Wiley Monographs in Crystallography. Wiley-Interscience [John Wiley & Sons], New York-Chichester-Brisbane, 1978
1978
-
[4]
Topological interlocking of platonic solids: A way to new materials and structures
A. Dyskin, Y. Estrin, A. Belov-Kanel, and E. Pasternak. “Topological interlocking of platonic solids: A way to new materials and structures”. In:Philosophical Magazine Letters - PHIL MAG LETT83 (Mar. 2003), pp. 197–203
2003
-
[5]
A new concept in design of materials and structures: assemblies of interlocked tetrahedron-shaped elements
A. V. Dyskin, Y. Estrin, A. Y. Kanel-Belov, and E. G. Pasternak. “A new concept in design of materials and structures: assemblies of interlocked tetrahedron-shaped elements”. In:Scripta Materialia44.12 (2001), pp. 2689–2694
2001
-
[6]
VoroNoodles: Topological Interlocking with Helical Layered 2-Honeycombs
M. Ebert, E. Akleman, V. Krishnamurthy, R. Kulagin, and Y. Estrin. “VoroNoodles: Topological Interlocking with Helical Layered 2-Honeycombs”. In:Advanced Engineering Materials26.4 (), p. 2300831. eprint:https://onlinelibrary.wiley.com/doi/pdf/10.1002/adem.202300831
-
[7]
Handlebody Plesiohedra Unchained: Topologically Interlocked Cell-Transitive 3-Honeycombs
M. Ebert, D. Kim, E. Akleman, and V. Krishnamurthy. “Handlebody Plesiohedra Unchained: Topologically Interlocked Cell-Transitive 3-Honeycombs”. In:Computer-Aided Design177 (2024), p. 103779
2024
-
[8]
Algorithms for crystallographic groups
B. Eick and B. Souvignier. “Algorithms for crystallographic groups”. In:International Journal of Quantum Chemistry106.1 (2006), pp. 316–343. eprint:https : // onlinelibrary . wiley .com / doi/pdf/10.1002/qua.20747
-
[9]
M. C. ( C. Escher.Fish, vignette. Print. Accessed October 24, 2025. Aug. 1954
2025
-
[10]
A. F. Frézier.La theorie et la pratique de la coupe des pierres et des bois, pour la construction des voutes et autres parties des bâtimens civils & militaires, ou Traité de stereotomie a l’usage de l’architecture. Vol. 2. Doulsseker, 1738. [11]GAP – Groups, Algorithms, and Programming, Version 4.16.0. The GAP Group. 2026
2026
-
[11]
Goertzen.Constructing Interlocking Assemblies with Crystallographic Symmetries
T. Goertzen.Constructing Interlocking Assemblies with Crystallographic Symmetries. 2024. arXiv: 2405.15080 [cs.CG]
-
[12]
Construction of Simplicial Surfaces with given Geometric Contraints
T. Goertzen. “Construction of Simplicial Surfaces with given Geometric Contraints”. To be sub- mitted. Dissertation. RWTH Aachen University, 2024
2024
-
[13]
Goertzen.Mathematical Foundations of Interlocking Assemblies
T. Goertzen.Mathematical Foundations of Interlocking Assemblies. 2024. arXiv:2405 . 17644 [math.CO]
2024
-
[14]
In- fluence of block arrangement on mechanical performance in topological interlocking assemblies: A study of the versatile block
T. Goertzen, D. Macek, L. Schnelle, M. Weiß, S. Reese, H. Holthusen, and A. C. Niemeyer. “In- fluence of block arrangement on mechanical performance in topological interlocking assemblies: A study of the versatile block”. In:International Journal of Solids and Structures306 (2025), p. 113102
2025
-
[15]
TopologicalInterlockingviaSymmetry
T.Goertzen,A.Niemeyer,andW.Plesken.“TopologicalInterlockingviaSymmetry””.In:Concrete innovation for sustainability In: Proceedings for the 6th fib International Congress. 2022, pp. 12– 16
2022
-
[16]
GRABCAD Community.Stanford Bunny
M. GRABCAD Community.Stanford Bunny. https://grabcad.com/library/stanford-bunny-solid- model. 2012
2012
-
[17]
Interlocking of convex polyhedra: towards a geometric theory of fragmented solids
A. Y. Kanel-Belov, A. V. Dyskin, Y. Estrin, E. Pasternak, and I. A. Ivanov-Pogodaev. “Interlocking of convex polyhedra: towards a geometric theory of fragmented solids”. In:Mosc. Math. J.10.2 (2010), pp. 337–342, 478–479
2010
-
[18]
Kopsky and D
V. Kopsky and D. B. Litvin, eds.International Tables for Crystallography, Volume E: Subperiodic groups. 5th. Vol. E. International Tables for Crystallography. Berlin, New York: Springer-Verlag, 2002
2002
-
[19]
Micciancio and S
D. Micciancio and S. Goldwasser.Complexity of Lattice Problems: A Cryptographic Perspective. The Springer International Series in Engineering and Computer Science. Springer US, 2002
2002
-
[20]
D-V cells and fundamental domains for crystallographic groups, algorithms, and graphic realizations
E. Molnár, I. Prok, and J. Szirmai. “D-V cells and fundamental domains for crystallographic groups, algorithms, and graphic realizations”. In: vol. 38. 7-9. Hungarian applied mathematics and computer applications. 2003, pp. 929–943. 14
2003
-
[21]
Percolation mechanism of failure of a planar assembly of interlocked osteomorphic elements
A. Molotnikov, Y. Estrin, A. Dyskin, E. Pasternak, and A. Belov-Kanel. “Percolation mechanism of failure of a planar assembly of interlocked osteomorphic elements”. In:Engineering Fracture Mechanics74 (May 2007), pp. 1222–1232
2007
-
[22]
A. C. Niemeyer, R. Akpanya, T. Görtzen, M. Weiß, L. Schnelle, and F. Fehre.GAPic GAP image creator, for visualizing structures, Version 0.1.https://github.com/GAP-ART-RWTH/GAPic. GAP package. Apr. 2023
2023
-
[23]
A. C. Niemeyer, R. Akpanya, and L. Schnelle.CrystFundDom Allows the computation of funda- mental domains via Dirichlet cells for given crystallographic group and starting point, Version 0.1. https://github.com/GAP-ART-RWTH/CrystFundDom. GAP package. July 2025
2025
-
[24]
Plesken.Kristallographische Gruppen, Summer semester
W. Plesken.Kristallographische Gruppen, Summer semester. 1994
1994
-
[25]
Plesken.Kristallographische Gruppen, Summer semester
W. Plesken.Kristallographische Gruppen, Summer semester. 2014
2014
-
[26]
Design and Structural Optimization of Topological Interlocking Assemblies
Z. Wang, P. Song, F. Isvoranu, and M. Pauly. “Design and Structural Optimization of Topological Interlocking Assemblies”. In:ACM Transactions on Graphics (SIGGRAPH Asia 2019)38.6 (2019). Article No. 193. A Proofs for completeness Theorem A.1.[25, Thm. III.11 (ii)] LetΓ≤E(n)be a crystallographic group. Ifu∈Rn is a point in general position forΓ, then the D...
2019
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.