Keywords: Crystallographic groups, algorithmic group theory, fundamental domains, topological interlocking

MSC: 20H15, 52B55, 52C22, 68U05, 20F65

1 Introduction↩︎

One definition of a crystallographic group \(\Gamma \leq \mathop{\mathrm{E}}(n)\) is that there exists a compact fundamental domain \(F \subset \mathbb{R}^n\) of \(\Gamma\), a compact subset which contains a system of representatives \(F^\circ \subseteq V \subseteq F\) for the natural action of \(\Gamma\) on \(\mathbb{R}^n\). Hence, a fundamental domain \(F\) of \(\Gamma\) allows us to tile the Euclidean space \(\mathbb{R}^n\) through the action of \(\Gamma\) on \(F\). This property makes crystallographic groups interesting not only from a purely mathematical perspective but also from an artistic one. For instance, the Dutch artist M.C.Escher exploited crystallographic groups in dimension \(2\) to create artworks that continue to fascinate both mathematicians and artists to this day (see [1] for examples of his work). In 1912, Bieberbach proved that there is only a finite number of crystallographic groups \(\Gamma\leq \mathop{\mathrm{E}}(n)\) for every \(n\in \mathbb{N}\), see [2]. Furthermore, for \(n\leq6\) all crystallographic groups of dimension \(n\) are known and enumerated (up to isomorphism). These groups, together with additional structural information such as standard generating sets, can be found in [3]. For instance, for \(n=2\) there exist exactly \(17\) crystallographic groups (wallpaper groups) and for \(n=3\) there are exactly \(230\) crystallographic groups (space groups).

Since the definition of a crystallographic group requires the existence of a compact fundamental domain, it is natural to ask how such a fundamental domain can be computed for a given crystallographic group \(\Gamma\leq \mathop{\mathrm{E}}(n)\). This problem is the focus of this paper. If \(\Gamma\) arises from a suitable generating set, we are able to answer this question by presenting an algorithm that computes Dirichlet cells forming fundamental domains of \(\Gamma\). (The choice of a suitable generating set of \(\Gamma\) is described in [not:cryst-grp-cosets].) A Dirichlet cell (also referred to as Voronoi domain) is a convex set in \(\mathbb{R}^n\) that can be constructed as the intersection of half spaces \(H^+(u,w):=\{v\in \mathbb{R}^n\mid \Vert u-v\Vert \leq \Vert w-v\Vert \}\) between points \(u\) and \(w\) in \(\mathbb{R}^n\), see 1. Loosely speaking, \(H^+(u,w)\) contains every point \(v\in \mathbb{R}^n\) that is closer to \(u\) than to \(w\) with respect to the Euclidean norm. For a given crystallographic group \(\Gamma\leq \mathop{\mathrm{E}}(n)\) and a point \(u\in \mathbb{R}^n\) satisfying \(\vert \mathrm{Stab}_{\Gamma}(u)\vert =1\), the intersection of all the half spaces \(H^+(u,w),\) where \(w\in u^\Gamma\), is a Dirichlet cell \(D(u,u^\Gamma)\) forming a fundamental domain of \(\Gamma\) (see Definition 1 and Appendix 4). Although \(\vert u^\Gamma \vert = \infty,\) there exist finitely many \(w_1,\ldots,w_\ell\in u^\Gamma\) such that \(D(u,u^\Gamma)=D(u,\{w_1,\ldots,w_\ell\}).\) In this work, we present an algorithmic approach for the construction of these elements by solving the word problem: We show that the points \(w_1,\ldots,w_\ell\) can be obtained from elements in \(\Gamma\) that can be written as words of bounded length in a suitable generating set of \(\Gamma.\) In particular, we prove the following theorem.

Note, existing algorithms to compute fundamental domains for a given crystallographic group rely on heuristic estimates for the number of elements in \(u^\Gamma\) that must be considered to determine \(D(u, u^\Gamma)\), see [4]. Here, we take a different approach by establishing the upper bound on the length of words using a suitably chosen generating set of \(\Gamma\) that need to be considered for this computation. Using this theorem together with some fundamental results, we are able to present Algorithm [alg:dirichletcell] to compute fundamental domains for crystallographic groups and employ it to compute some fundamental domains of crystallographic groups of dimension \(3\). Moreover, we use these theoretical results and illustrate an approach for the construction of geometries in \(\mathbb{R}^3\) that have the potential to generate topological interlocking assemblies. Note, our algorithm relies on the following assumptions:

1. The knowledge of a point \(u \in \mathbb{R}^n\) with \(\lvert \mathrm{Stab}_{\Gamma}(u) \rvert = 1\), and

2. Knowledge of a generating set of \(\Gamma\), as described in [not:cryst-grp-cosets].

In our investigations, we apply the algorithm to crystallographic groups \(\Gamma \le \mathop{\mathrm{E}}(n)\) with \(n=3\). Groups of \(n\leq 4\) which satisfy the requirements of [not:cryst-grp-cosets] can be found in [3]. Moreover, for any crystallographic group the stabiliser of almost every point \(u \in \mathbb{R}^n\) is trivial. Hence, the assumptions required for our method are naturally satisfied in this setting.

This paper is structured as follows: In Section 2 we introduce notions on crystallographic groups and Dirichlet domains that are essential for the understanding of this paper. Next, we derive the theory to establish our algorithm for the computation of fundamental domains in 3. For this, we have to investigate points in general position for a given crystallographic group (see 2) and their resulting Dirichlet domains. We exploit our results to establish 2. In order to present our proposed algorithm, we further comment on the volume of a fundamental domain of \(\Gamma.\) Lastly, we discuss the construction of topological interlocking assemblies, see 4. Inspired by the constructions in [5], [6] we give a construction of three dimensional geometries that have a high potential of facilitating topological interlocking assemblies.

Note, it appears that some of the results used in this work are known to the community, although we could not find explicit references. For completeness and clarity, we include proofs of these results in the appendix.

2 Preliminaries↩︎

In order to introduce the framework of this work and present our results, we use the following definitions: Let \(n\geq 2\) be a natural number and \(v,w\) elements in \(\mathbb{R}^n\). Then we denote the Euclidean scalar product of \(v\) and \(w\) by \(\langle v, w \rangle\) and define the Euclidean norm of \(v\) by \(\Vert v \Vert \mathrel{\vcenter{:}}= \sqrt{\langle v, v \rangle}\). As usual, the norm \(\Vert \cdot \Vert\) induces a metric on \(\mathbb{R}^n\) via \(d(v, w) \mathrel{\vcenter{:}}= \Vert v - w \Vert\). For \(r\in \mathbb{R}_{>0}\) we define the open \(r\)-ball of \(v\) as \(B_r(v) \mathrel{\vcenter{:}}= \{ w \in \mathbb{R}^n \mid d(v, w) < r \}.\) We call a map \(\varphi: \mathbb{R}^n \to \mathbb{R}^n\) an isometry, if it is distance preserving, i.e.\(d(v^\varphi, w^\varphi) = d(v, w)\) for all \(v, w \in \mathbb{R}^n\). The set \(\mathop{\mathrm{E}}(n)\) of all isometries of \(\mathbb{R}^n\) forms a group called the Euclidean group of dimension \(n.\) A subset \(F\subseteq \mathbb{R}^n\) is called a fundamental domain of a group \(\Gamma\leq \mathop{\mathrm{E}}(n)\), if (i) \(\bigcup_{\gamma \in \Gamma} F^{\gamma} = \mathbb{R}^n\) and (ii) there is a system of representatives \(V \subseteq \mathbb{R}^n\) of the orbits of \(\Gamma\) on \(\mathbb{R}^n\) such that \(F^\circ \subseteq V \subseteq F.\) The group \(\Gamma\) is called a crystallographic group, if \(\Gamma\) is a discrete subgroup of \(\mathop{\mathrm{E}}(n)\) (this means that \(v^\Gamma\) is discrete in \(\mathbb{R}^n\) for all \(v \in \mathbb{R}^n\)) and there exists a compact fundamental domain of \(\Gamma\). Note, that fundamental domains of given crystallographic groups do not have to be connected. However, we assume all fundamental domains in this paper to be connected. We refer the reader to [7] for further theoretical background and algorithmic methods for the investigation of crystallographic groups.

Note, the Euclidean group \(\mathop{\mathrm{E}}(n)\) is isomorphic to the semidirect product \(\mathop{\mathrm{O}}(n) \ltimes \mathbb{R}^n\), where \(\mathop{\mathrm{O}}(n)\) denotes the orthogonal group of dimension \(n\). The existence of an isomorphism \(\Psi:\mathop{\mathrm{E}}(n)\to \mathop{\mathrm{O}}(n) \ltimes \mathbb{R}^n\) allows us to interpret the isometry \(\varphi\in \mathop{\mathrm{E}}(n)\) as a tuple \(\Psi(\varphi)=(\varphi_o,\varphi_t)\in \mathop{\mathrm{O}}(n) \ltimes \mathbb{R}^n,\) where we call \(\varphi_o \in \mathop{\mathrm{O}}(n)\) the orthogonal component and \(\varphi_t \in \mathbb{R}^n\) the translational component of \(\varphi\). The action of \((\varphi_o,\varphi_t)\) on a point \(u \in \mathbb{R}^n\) is given by \(u^{(\varphi_o, \varphi_t)} = u\cdot{\varphi_o} + \varphi_t\). Here, we choose \(\Psi\) to be an isomorphism such that \(v^\varphi= v^{\Psi(\varphi)}\) holds for all \(v\in \mathbb{R}^n.\) Examples of isometries of the Euclidean space \(\mathbb{R}^2\) are given by the elements \(\varphi,\psi\in \mathop{\mathrm{E}}(2)\) defined as follows: \[\Psi(\varphi):= \left( \begin{pmatrix} -1 &0 \\ 0 &-1\end{pmatrix}, \begin{pmatrix} 0 \\ 0 \end{pmatrix}\right), \Psi(\tau_1):= \left( \begin{pmatrix} 1 &0 \\ 0 &1\end{pmatrix}, \begin{pmatrix} 1 \\ 0 \end{pmatrix}\right), \Psi(\tau_2):= \left( \begin{pmatrix} 1 &0 \\ 0 &1\end{pmatrix}, \begin{pmatrix} 0 \\ 1 \end{pmatrix}\right).\] These two elements generate the wallpaper group \(p2=\langle \varphi, \tau_1, \tau_2 \rangle\) (using the naming from international notation [8]). For a better understanding of the action of this group, we give Figure 1. This figure illustrates the action of \(p2\) on \(\mathbb{R}^2.\) If \(M\) is the set of black dots forming the letter \(\beta\) in the upper rectangle situated in the middle of the described figure, then \(M^{p2}\) is given by all the black \(\beta\) tiling the plane as indicated in Figure 1.

We say that \(v\in \mathbb{R}^n\) is in special position for a crystallographic group \(\Gamma\leq \mathop{\mathrm{E}}(n)\), if \(\mathrm{Stab}_{\Gamma}(v) \neq \{\mathop{\mathrm{Id}}\}\). If the stabiliser of \(v\) is trivial, then \(v\) is said to be in general position for \(\Gamma\). For instance, the point \(v=(1,1)^t\in \mathbb{R}^2\) forms a point in special position for the group \(p2.\) This can be verified by the computation \(v^{\varphi\cdot \tau_1 \cdot \tau_1 \cdot \tau_2 \cdot \tau_2} ={(( -1,-1)^t)}^{\tau_1 \cdot \tau_1 \cdot \tau_2 \cdot \tau_2}=v\). Moreover, we define the translation (normal) subgroup of \(\Gamma\) as \(\mathcal{T}(\Gamma) \mathrel{\vcenter{:}}= \{ (\varphi_o, \varphi_t) \in \Gamma \mid \varphi_o = \mathop{\mathrm{Id}}\}\). The set \(\mathcal{L}(\Gamma) \mathrel{\vcenter{:}}= \{\varphi_t \mid (\varphi_o, \varphi_t) \in \mathcal{T}(\Gamma) \}\) is a full lattice of dimension \(n\) satisfying \(\mathcal{T}(\Gamma) \cong \mathcal{L}(\Gamma)\). Additionally, the point group of \(\Gamma\) is defined as the quotient \(\mathcal{P}(\Gamma) \mathrel{\vcenter{:}}= \Gamma / \mathcal{T}(\Gamma)\). If this quotient group is isomorphic to a subgroup of \(\Gamma\), then we call \(\Gamma\) symmomorphic.

Previously we have introduced half spaces between different points in \(\mathbb{R}^n\). Now, we use this definition to formally introduce Dirichlet domains.

3 Computing fundamental domains↩︎

The aim of this section is to present an algorithm that allows us to compute a fundamental domain for a given crystallographic group. Our algorithm requires as input a point \(u\in \mathbb{R}^n\) in general position for a given crystallographic group. This point is then used to construct a Dirichlet cell forming a fundamental domain for \(\Gamma.\) The details can be found in Algorithm [alg:dirichletcell]. In order to achieve this goal, we need some preparation. We start by examining points in special and general position for \(\Gamma\). First, since a fundamental domain \(F\) contains a system of representatives \(V\) satisfying \(F^{\circ}\subseteq V \subseteq F\), we obtain the following lemma as a direct consequence.

*

We prove the above statement by contradiction and therefore assume that \(v\) is a point in special position satisfying \(v\in F^{\circ}.\) These two conditions imply that there exists a non-trivial \(\alpha=(\alpha_o,\alpha_t) \in \mathrm{Stab}_\Gamma(v)\) and \(\delta \in \mathbb{R}_{>0}\) such that \(v^\alpha=v\) and \(B_\delta(v) \subset F^\circ\). We claim that there is a point \(w \in B_\delta(v)\) such that \(w^\alpha \neq w\). In order to show this, we assume that \(w^\alpha = w\) holds for all \(w \in B_\delta(v)\). Thus, for \(1\leq i \leq n\) we define the point \(w_i\) as \(w_i \mathrel{\vcenter{:}}= v + \frac{\delta}{2} e_i\), where \(e_i\) is the \(i\)-th standard basis vector. Since \(d(w_i, v) < \delta\) for all \(1 \leq i \leq n,\) the points \(w_1,\ldots,w_n\) are all contained in \(B_\delta(v)\). That means \(w_i^\alpha = w_i\) by our assumption. Thus, we obtain \[\begin{align} v+\tfrac{\delta}{2}e_i &= w_i = w_i^\alpha = \left(v+\tfrac{\delta}{2}e_i \right) \cdot \alpha_o + \alpha_t = (v\cdot{\alpha_o} + \alpha_t) + \tfrac{\delta}{2}e_i\cdot \alpha_o =v^\alpha + \tfrac{\delta}{2}e_i\cdot \alpha_o = v +\tfrac{\delta}{2}e_i\cdot \alpha_o \end{align}\] for all \(1 \leq i \leq n\). Thus, \(e_i=e_i\cdot \alpha_o.\) Since \(e_1,\ldots,e_n\) is a basis of \(\mathbb{R}^n\), the orthogonal component of \(\alpha\) satisfies \(\alpha_o = \mathop{\mathrm{Id}}\). This implies \(\alpha \in \mathcal{T}(\Gamma)\). Now, \(\alpha\) is a non-trivial translation, hence we get \(w^\alpha\neq w\) and therefore \(w^\alpha \notin F^\circ\) by Lemma 1. This results in \(w^\alpha \notin B_{\delta}(v)\) which contradicts \(w^\alpha = w\) for all \(w \in B_\delta(v)\). Thus, there exists a \(w \in B_\delta(v) \setminus \{ v \}\) such that \(w^\alpha \neq w\). Since \(\alpha\) is an isometry of \(\mathbb{R}^n,\) we conclude that \(d(v, w^\alpha)= d(v^\alpha, w^\alpha) =d(v,w) < \delta\) i.e.\(w^\alpha \in B_{\delta}(v) \subset F^\circ\) holds. Hence, two elements in the \(\Gamma\)-orbit of \(w\) are contained in \(F^\circ\), namely \(w^\alpha\) and \(w\). This contradicts \(F\) being a fundamental domain for \(\Gamma\).

Next, we establish a correspondence between the Dirichlet cells of points in general position that lie in the same \(\Gamma\)-orbit.

*

Let \(\gamma \in \Gamma\) be an isometry of \(\mathbb{R}^n\). We start this proof by showing \(D(u^\gamma,u^\Gamma)\subseteq D(u,u^\Gamma)^\gamma.\) Thus, let \(v\in \mathbb{R}^n\) be a point in \(D(u^\gamma, u^\Gamma)\). That means that \(d(u^\gamma, v) \leq d(w,v)\) for all \(w \in u^\Gamma\). We define \(\tilde{v} \mathrel{\vcenter{:}}= v^{\gamma^{-1}}\). Since \(\gamma\) is an isometry, we obtain \[\begin{align} d(u, \tilde{v}) = d(u^\gamma, \tilde{v}^\gamma)= d(u^\gamma, (v^{\gamma^{-1}})^\gamma) = d(u^\gamma, v) \leq d(w, v) = d(w^{\gamma^{-1}}, v^{\gamma^{-1}}) = d(w^{\gamma^{-1}}, \tilde{v}). \end{align}\] for all \(w \in u^\Gamma\). Note, the above inequality holds for all \(w^{\gamma^{-1}} \in u^\Gamma\). Thus \(\tilde{v} \in D(u, u^\Gamma)\) which implies \(v = (v^{\gamma^{-1}})^\gamma \in D(u, u^\Gamma)^\gamma\). Now, let \(v'\) be a point in \(D(u, u^\Gamma)^\gamma\). Hence, there is a \(v \in D(u, u^\Gamma)\) such that \(v^\gamma = v'\). As described in the above case, we can use the isometry \(\gamma\) to conclude: \[d(u^\gamma, v') = d(u^\gamma, v^\gamma) = d(u, v) \leq d(w, v) = d(w^\gamma, v^\gamma) = d(w^\gamma, v')\] for all \(w \in u^\Gamma\). Since the above inequality holds for all \(w^\gamma \in u^\Gamma\), we get \(v' \in D(u^\gamma, u^\Gamma)\).

Now, we are able to state 1, which forms the basis of our proposed algorithm. This theorem establishes that the Dirichlet cell that is constructed for a point in general position for a crystallographic group forms a fundamental domain for the given group. This result can already be found in [10]. In Appendix 4, we give a proof of this statement for completeness.

With Theorem 1 in place, our approach for computing Dirichlet cells in the given setting is now justified. To make practical use of this result, we have to derive a formulation of this statement that is computationally applicable. First, we have to argue that only finitely many points in \(u^\Gamma\) are required to construct \(D(u,u^\Gamma)\) if \(u\) is in general position for \(\Gamma\leq \mathop{\mathrm{E}}(n)\). Additionally, we have to show that these points arise from the action of elements in \(\Gamma\) that can be written as words of bounded length with respect to an appropriate generating set. The choice of such a generating set is detailed below.

With a generating set \(S\) as described above, we can show that the translations in \(\Gamma\) induced by points with a bounded norm can be written as words in \(S\) of bounded length. The length can be bounded by vectors related to the lattice basis.

If we define \(\Vert C\Vert_{2,1} := \sum_{i=1}^n \Vert c_i\Vert\) for a matrix \(C\in \mathbb{R}^{n\times n}\) with rows \(c_1, \ldots, c_n,\) then we obtain the following result.

*

By [not:cryst-grp-cosets], \(\{\tau_k\mid k \in K\}\) generates the translation normal subgroup \(\mathcal{T}(\Gamma)\). Further, we know that \(\mathcal{T}(\Gamma)\) satisfies \(\mathcal{T}(\Gamma) \cong \mathcal{L}(\Gamma)\). Since the ball \(B_\delta(0)\) contains only finitely many lattice points in \(\mathcal{L}(\Gamma)\), the set \(M_{\delta}:=\{\tau \in \mathcal{T}(\Gamma)\mid \Vert(\tau)_t\Vert \leq \delta\}\) is finite. Furthermore, for every \(\tau \in M_\delta\), there exists a set of coefficients \(\{a_k \in \mathbb{Z}\mid k \in K \}\) such that \[\tau = \prod_{k \in K} \tau_k^{a_k}.\] Hence, every \(\tau\in M_{\delta}\) can be written as a word in \(\{\tau_k\mid k \in K\}\) of length at most \(A(\delta),\) where \(A(\delta)\) is defined as \[\label{eq:A40delta41} A(\delta) \mathrel{\vcenter{:}}= \max \left\{ \sum_{k \in K} | a_k| \, \middle| \, \tau = \prod_{k \in K} {\tau_k}^{a_k} \in M_{\delta} \right\}.\tag{1}\] For \(\tau \in M_\delta\) with \(\tau = \prod_{k \in K} \tau_k^{a_k}\) define \(a := (a_1, \ldots, a_n)^T\). Then \(a = B \cdot (\tau)_t\) where \(B\) is the reciprocal lattice matrix. If \(b_i\) denotes the \(i\)-th row of \(B\), we find by the Cauchy-Schwarz inequality: \[\Vert a\Vert_1 = \sum_{k=1}^n |a_k| \le \sum_{k=1}^n \Vert b_k\Vert \cdot \Vert \tau_t \Vert = \Vert B\Vert_{2,1} \cdot \delta.\] Therefore \(A(\delta) \le \Vert B\Vert_{2,1} \cdot \delta.\)

Now, we exploit this result and approach the word problem for arbitrary isometries. For this, we give the following remark which introduces a new notation and recalls an identity for the Dirichlet cell of a point in general position from [10].

Hence, if \(r\) is given as in the above remark, then we have to find all elements in the set \(W_{2r}(u)\) to compute a Dirichlet cell of a crystallographic group \(\Gamma\).

Note that \(D(u, u^{\Gamma}) \subseteq D(u, u^{\mathcal{T}(\Gamma)})\) as \(\mathcal{T}(\Gamma) \leq \Gamma\). The covering radius \(r\) of a lattice is defined as the smallest radius \(r>0\) such that balls of radius \(r\) centred at all lattice points cover the entire space \(\mathbb{R}^n\). Therefore, if \(r\) is the covering radius of the lattice induced by \(\mathcal{T}(\Gamma)\) it follows that \(D(u, u^{\Gamma})\) is contained in a ball of radius \(r\) around \(u\). Combining this with the inequality from [11] we obtain the following upper bound: \[r \leq \frac{\sqrt{n}}{2} \max_{k \in K} || \tau_k||.\]

Before concluding the main result, we need an additional lemma.

*

Let \(w\in W_d(u)\), that is there exists an element \(\gamma\in \Gamma\) such that \(w = u^\gamma\) and \(\Vert w - u \Vert < d\). Since \(S\) is a generating set as described in [not:cryst-grp-cosets], we can write \(\gamma\) as \(\gamma = \rho_i \tau\) for an \(i \in I\) and \(\tau \in \mathcal{T}(\Gamma)\). We prove the above statement by contradiction. Hence, we assume \(w \notin \widehat{W}_{d+ \varepsilon}(u)\), i.e.\(\Vert\tau_t\Vert > d+\varepsilon\). By using the inequality \(\Vert \tau_t \Vert > d + \varepsilon> \varepsilon\geq \Vert u^{\rho_i} - u \Vert\), we obtain \[\begin{align} \Vert w - u \Vert = \Vert u^{\rho_i} + \tau_t - u \Vert \geq \left| \Vert \tau_t \Vert - \Vert u^{\rho_i} - u\Vert \right| = \Vert \tau_t \Vert - \Vert u^{\rho_i} - u\Vert \geq \Vert \tau_t \Vert - \varepsilon>d. \end{align}\] This implies \(w\notin W_d(u)\), contradicting our choice of \(w\).

By combining 3 and 4 we are able to establish the desired upper bound of the word length.

*

Consider \(\widehat{W}_{d+\varepsilon}(u)\) as defined as in 2, and define \(d: = 2r\). By Lemma 4 the Dirichlet cell around the point \(u\) is equal to the intersection: \[D(u, u^\Gamma) = \bigcap_{w \in W_d(u)} H^+(u,w) = \bigcap_{w \in \widehat{W}_{d+\varepsilon}(u)} H^+(u, w).\]

By the choice of our generating set \(S\), we know that \(w \in \widehat{W}_{d+\varepsilon}(u)\) satisfies \(w = u^\gamma\) for an element \(\gamma = \rho_i \tau\) with \(i \in I\) and \(\Vert\tau\Vert\leq d+\varepsilon\).

Since \(\tau\) is a word in \(\{ \tau_k \mid k \in K \}\) with \(|| (\tau)_t || < d+\varepsilon\) (see 3), it follows that \(\gamma=\rho_i\tau\) is a word in \(S\) of length at most \(A(d+\varepsilon)+1.\)

If \(\Gamma\) is symmorphic we can additionally use Lemma 3 and Remark [rem:epsilon] to obtain the following bound:

\[A(2r+\varepsilon)+1 \le A(2(\rho +\Vert u\Vert)) + 1 \le 2\cdot \Vert B \Vert_{2,1} \cdot \frac{\sqrt{n}}{2} \max_{k \in K} || \tau_k|| + 1.\]

Hence, for a symmomorphic crystallographic group and a corresponding point in general position as described in the statement of the theorem above, it suffices to consider words of length at most \(2\cdot \Vert B \Vert_{2,1} \cdot \frac{\sqrt{n}}{2} \max_{k \in K} || \tau_k|| + 1\) in order to compute the corresponding Dirichlet cell forming a fundamental domain. In the examples we have computed, however, the resulting upper bound \(2\cdot \Vert B \Vert_{2,1} \cdot \frac{\sqrt{n}}{2} \max_{k \in K} || \tau_k|| + 1\) is often larger than necessary. For instance, if we assume that for a given symmomorphic crystallographic group \(\Gamma\) the point \(u=0\) is in general position and the basis in dimension \(n=3\) is the standard basis, then we obtain \(2\cdot \Vert B \Vert_{2,1} \cdot \frac{\sqrt{n}}{2} \max_{k \in K} || \tau_k|| + 1 \leq 7\). In all computed examples, no word length greater than \(5\) was required, and in many cases a length of \(4\) already sufficed. If e.g. the size of of a given generating set is \(4\) we get a set of element to consider of size \(4^7 = 16384\), however in practice considering \(4^4 = 256\) elements was enough.

Thus, Dirichlet cells forming fundamental domains of \(\Gamma\) can be computed by considering elements in \(\Gamma\) expressible as words of bounded length in a suitable generating set.

In order to optimise our proposed algorithm for the computation of fundamental domains, we add another ingredient. This is based on the following observation: Let \(\Gamma\leq \mathop{\mathrm{E}}(n), S\) and \(u\) be given as in [not:cryst-grp-cosets] and \(\varepsilon\mathrel{\vcenter{:}}= \max_{i \in I} \Vert u^{\rho_i} - u\Vert\) as described in 4. We then choose a positive real number \(r_1\) such that the set \[D_1 = \bigcap_{w \in \widehat{W}_{2r_1}(\varepsilon)} H^+(u, w).\] is a convex polytope in \(\mathbb{R}^n\), see 4 for the definition of the set \(\widehat{W}_{2r_1}(\varepsilon)\). It is easy to see that \(D_1\) satisfies \(D(u,u^\Gamma)\subseteq D_1.\) However, in order to know if this inclusion is already an equality we give a volume argument. In particular, we will see in the following that every fundamental domain for \(\Gamma\) has the same volume (3). Here, the volume \(\mathrm{vol}(B)\) of a set \(B\subseteq \mathbb{R}^n\) is defined as the Lebesgue measure of \(B\). Hence, if \(D_1\) satisfies \(\mathrm{vol}(D(u,u^\Gamma))< \mathrm{vol}(D_1)\), we have to choose a positive real number \(r_2>r_1\) and construct the polytope \(D_2\) given by \[D_2 \mathrel{\vcenter{:}}= \bigcap_{w \in \widehat{W}_{2r_2}(\varepsilon)} H^+(u, w).\] This process can be iterated. Hence, we will obtain radii \(r_1< r_2 < r_3< \ldots\) such that for every \(i \in \mathbb{N}\) the positive number \(r_i\) gives rise to the polytope \[D_i = \bigcap_{w \in \widehat{W}_{2r_i}(\varepsilon)} H^+(u, w).\]

If the incrementation of the radii is chosen carefully (\(r_{i+1}>r_i+1\) for instance), we will obtain a smallest index \(m\) such that \(\mathrm{vol}(D_m)=\mathrm{vol}(D(u,u^\Gamma)).\) Since \(D_m\) and \(D(u,u^\Gamma)\) are compact sets with \(D(u,u^\Gamma)\subseteq D_m\), this implies \(D_m=D(u,u^\Gamma)\) and we have therefore computed our fundamental domain.

The remainder of this section is devoted to establishing 3 and giving a pseudocode describing our algorithm. First, it is easy to see that applying isometries to subsets of \(\mathbb{R}^n\) leaves the corresponding volumes invariant.

Next, we establish a relation between fundamental domains of a crystallographic group \(\Gamma\) and fundamental domains of the translation normal subgroup \(\mathcal{T}(\Gamma).\)

Note, we call the set \(C\) in the above statement a translation cell of \(\Gamma\). In [apx:prop:translation-cell-fund-dom] we provide a proof of this statement in the appendix and proceed by computing the volume of a fundamental domain.

*

We know that a translation cell is a fundamental domain for \(\mathcal{T}(\Gamma)\) (see Proposition [prop:translation-cell-fund-dom]). We observe that \(C\) contains \(|I|\) copies of the fundamental domain \(F\). Since these copies are intersection free sets that lie inside \(C\), we obtain the above equality.

With the above result, we are able to reduce the computation of the volume of a fundamental domain for \(\Gamma\) to computing the volume of the translation cell without computing the fundamental domain itself. Since the volume of the translation cell of \(\Gamma\) is the determinant of the lattice \(\mathcal{L}(\Gamma)\), obtaining the desired volume is straight forward.

By combining this observation with 2 we are able to give our proposed algorithm.

Algorithm [alg:dirichletcell] is implemented in the computer algebra system GAP [12] and is available via the package CrystFundDom [13], with additional visualisations available through GAPic [14].

4 Constructing Topological Interlocking Assemblies↩︎

In this section, we explore potential applications of 3-dimensional crystallographic groups. For this purpose, we make use of our results in 3. Our aim is to exploit a given 3-dimensional crystallographic group and construct a corresponding fundamental domain such that copies of this fundamental domain can be arranged in Euclidean 3-space into a so-called topological interlocking assembly (TIA). In order to give a brief description of a topological interlocking assembly, we have to recall some notions from [5]. The definition of a block is a non-empty subset \(X \subset \mathbb{R}^3\) that is connected, compact and further satisfies \(X= \overline{{X^\circ}}\). An assembly \(M\) is a countable set of blocks such that any two distinct blocks \(X,X'\in M\) satisfy \(X\cap X'= \partial X\cap \partial X'\). A frame \(J\) of a given assembly \(M\) is a proper non-empty subset of \(M\). Furthermore, a motion is a continuous map \(\varphi:[0,1]\to \mathop{\mathrm{SE}}(3)\) with \(\varphi(0)=Id\), where \(\mathop{\mathrm{SE}}(3)\) denotes the group of Euclidean motions. Then (loosely speaking), a topological interlocking assembly (TIA) is an assembly of blocks constrained by a fixed frame \(J\) such that every finite non-empty subset of blocks cannot be moved by continuous motions without causing intersections. In the literature, much attention has been given to investigations involving multiple copies of the same block, see [15], [16]. As an example, Dyskin et.al have utilised the Platonic solids to construct TIAs and have further explored the mechanical properties of the resulting assemblies [17].

The study of TIAs dates back to the 18th century. Early studies on TIAs can be found in the works of Abeille in 1735 [18] and Frezier in 1738 [19]. Since the impactful work of Dyskin et al.[20], who have reintroduced TIAs as a material design concept, planar TIAs have been studied extensively, see [21]–[24]. Although TIAs are widely used in civil engineering and architecture, there has been less investigation of these assemblies from a purely mathematical perspective. The first (mathematically) exact definition of a TIA was given in [6]. T.Goertzen [5], [25] explored TIAs that have been constructed by exploiting 2-dimensional crystallographic groups. Inspired by these works, we explore the construction of TIAs by employing 3-dimensional crystallographic groups. Note, another approach to construct three dimensional TIAs has been presented in [26] which constructs handlebody plesiohedra. Our approach can be summarised as follows.

Note, the group elements \(\varphi_i\) with \(i\in I\) can be chosen depending on the application of the desired TIA. In the following we will consider the crystallographic group \(p23\) and give two different sets of group elements to construct candidates of TIAs: one realising a tripod (see 6) and another one approximating the Stanford Bunny (see 4).

Step 2 of our described approach requires that a convex fundamental domain for a given crystallographic group can be transformed into a non-convex fundamental domain for the same group. This is achieved by the deformation of a fundamental domain as described below.

In the following, we give an example of a fundamental domain obtained from 3. In particular, we illustrate our method to construct assemblies that have a high potential of being TIAs by using the crystallographic group \(p23\leq \mathop{\mathrm{E}}(3)\). In order to define \(p23\), let \(\rho_i,\tau_i\) for \(i=1,2,3\) be isometries in \(\mathop{\mathrm{E}}(3)\) given by \[\begin{align} &\rho_1 \mathrel{\vcenter{:}}= \left( \begin{pmatrix} 0& 1& 0\\ 0& 0& 1\\ 1& 0& 0 \end{pmatrix}, \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \right), &&\rho_2 \mathrel{\vcenter{:}}= \left( \begin{pmatrix} -1& 0& 0\\ 0& 1& 0\\ 0& 0& -1 \end{pmatrix}, \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \right),\\ &\rho_3 \mathrel{\vcenter{:}}= \left( \begin{pmatrix} -1& 0& 0\\ 0& -1& 0\\ 0& 0& 1 \end{pmatrix}, \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \right), &&\tau_1 \mathrel{\vcenter{:}}= \left( \begin{pmatrix} 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 0 \end{pmatrix} \right),\\ &\tau_2 \mathrel{\vcenter{:}}= \left( \begin{pmatrix} 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{pmatrix}, \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix} \right), &&\tau_3 \mathrel{\vcenter{:}}= \left( \begin{pmatrix} 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1 \end{pmatrix}, \begin{pmatrix} 0\\ 0\\ 1 \end{pmatrix}\right). \end{align}\] These elements generate the group \(p23\), hence \(p23 \mathrel{\vcenter{:}}= \langle \rho_1, \rho_2, \rho_3, \tau_1, \tau_2, \tau_3 \rangle.\) If we consider the point \(u \mathrel{\vcenter{:}}= ( \frac{1}{4} \; \frac{1}{8} \;\frac{1}{4})^t\in \mathbb{R}^3\) and apply Algorithm [alg:dirichletcell] with the group \(p_{23}\) given by the above generators as input, we obtain a fundamental domain \(D_{23}\) given by the convex hull of the following points \[\left\{ \begin{pmatrix} -\frac{1}{2} \\ -\frac{1}{2} \\ -\frac{1}{2} \end{pmatrix}, \begin{pmatrix} -\frac{1}{3} \\ -\frac{1}{3} \\ -\frac{2}{3} \end{pmatrix}, \begin{pmatrix} 0 \\ 0\\ -\frac{1}{2} \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} -\frac{1}{2} \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} -\frac{1}{3} \\ \frac{1}{3} \\ -\frac{1}{3} \end{pmatrix}, \begin{pmatrix} -\frac{1}{2} \\ 0 \\ -\frac{1}{2} \end{pmatrix}, \begin{pmatrix} -\frac{2}{3} \\ -\frac{1}{3} \\ -\frac{1}{3} \end{pmatrix}, \begin{pmatrix} -\frac{1}{4} \\ -\frac{1}{4} \\ -\frac{1}{4} \end{pmatrix} \right\}.\]

A visualisation of the fundamental domain \(D_{23}\) in three different views can be found in Figure 2.

Next, we deform \(D_{23}\) to obtain a non-convex fundamental domain \(F_{23}\). As described in 3 we can obtain a new fundamental domain for \(p23\) by applying a deformation to \(D_{23}.\) The resulting fundamental domain \(F_{23}\) of \(p23\) is illustrated in the below figure.

Since \(F_{23}\) is a fundamental domain for \(p23\), and hence space-filling, we can create assemblies consisting of copies of \(F_{23}\) by exploiting the group \(p23\) as described in 3. By only choosing a subset of the blocks we can approximate arbitrary surfaces. To demonstrate this, we approximated the Stanford bunny ([27]). This approximation is achieved with \(1323\) blocks forming copies of \(F_{23}\). Note, the approximation could be refined by considering lower scaled fundamental domains and thus more blocks to approximate the shape. The resulting assembly is shown in Figure 4.

Additionally the deformation can also be performed in a non-linear manner such that the resulting fundamental domain has curved faces. To illustrate this, we present a deformation of the same fundamental domain of group \(p23\) in Figure 5. Note, that the resulting fundamental domain still retains the fundamental domain property and in particular can fill \(\mathbb{R}^3\) without overlapping.

Using the crystallographic group \(p23\) to arrange copies of \(F_{23}\) in Euclidean \(3\)-dimensional space opens up the construction of various assemblies. To illustrate this instance, we present the assembly shown in Figure 6. This assembly of blocks realises a tripod which we conjecture to be a TIA. Our hypothesis is strengthened by the fact that 3D-printed blocks with the frame (bottom blocks touching the ground) hold in place, suggesting they possess the interlocking property. Note, we have not proven that the two assemblies presented above are indeed TIAs. Here, we have illustrated these examples to showcase the rich design space of our approach. To verify the interlocking property of these assemblies, we have to employ expensive numerical computations as described in [22], [24]. Establishing such a proof will be the focus of future work.

Acknowledgement↩︎

The authors would like to thank Bernd Souvignier for valuable discussions and for drawing our attention to some relevant literature. The authors acknowledge the funding by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) in the framework of the Collaborative Research Centre CRC/TRR 280 “Design Strategies for Material-Minimized Carbon Reinforced Concrete Structures – Principles of a New Approach to Construction” (project ID 417002380). Furthermore, R.Akpanya was supported by a grant from the Simons Foundation (SFI-MPS-Infrastructure-00008650, JV).

5 Proofs for completeness↩︎

*

We first show that \[\mathbb{R}^n = \bigcup_{\gamma \in \Gamma} D(u, u^\Gamma)^\gamma.\] By 2, this is equivalent to proving \[\mathbb{R}^n = \bigcup_{\gamma \in \Gamma} D(u^\gamma, u^\Gamma).\] The union of Dirichlet cells on the right-hand side of the above equation forms a subset of \(\mathbb{R}^n\). Hence, it remains to show that \(\mathbb{R}^n \subseteq \bigcup_{\gamma \in \Gamma} D(u^\gamma, u^\Gamma)\) holds. Let therefore \(v \in \mathbb{R}^n\) be a point. We know that \(v\) is inside the cell \(D(u^{\gamma'},u^\Gamma)\), where \(\gamma'\in \Gamma\) such that \(d(u^{\gamma'}, v) \leq d(u^\beta, v)\) holds for all \(\beta \in \Gamma\). This implies \[v \in D(u^{\gamma'}, u^\Gamma) \subseteq \bigcup_{\gamma \in \Gamma} D(u^\gamma, u^\Gamma) = \bigcup_{\gamma \in \Gamma} D(u, u^\Gamma)^\gamma.\]

Next, we prove \(D(u^\alpha, u^\Gamma) \cap D(u^\beta, u^\Gamma) =\emptyset\) for distinct \(\alpha, \beta \in \Gamma\). We show this statement by contradiction and assume that there exist distinct \(\alpha, \beta \in \Gamma\) such that there exists \(v \in \left( D(u^\alpha, u^\Gamma) \right)^\circ \cap \left(D(u^\beta, u^\Gamma)\right)^\circ\). This implies \(d(v, u^\alpha) < d(v, u^\gamma)\) for all \(\gamma \in \Gamma \setminus \{ \alpha \}\) and \(d(v, u^\beta) < d(v, u^\delta)\) for all \(\delta \in \Gamma \setminus \{ \beta \}\). Since these inequalities hold for all elements in \(\Gamma\), the inequalities \(d(v, u^\alpha) < d(v, u^\beta)\) and \(d(v, u^\beta) < d(v, u^\alpha)\) follow. This is a contradiction.
Now, we have to verify that \(D(u,u^\Gamma)\) contains a system of representatives of the action of \(\Gamma\) on \(\mathbb{R}^n\). We start by showing that at least one point of each orbit is contained in \(D(u,u^\Gamma).\) For this, let \(v \in \mathbb{R}^n\) be a point and \(w \in v^\Gamma\) the point satisfying \[w \mathrel{\vcenter{:}}= \mathop{\mathrm{argmin}}_{\hat{w} \in v^\Gamma} \{ d( \hat{w}, \hat{u} ) \mid \hat{u} \in u^\Gamma \}.\] That means, \(w\) is the point in the orbit of \(v\) with minimum distance to the orbit of \(u\). Furthermore, let \(\alpha \in \Gamma\) be the group element so that \(w\) is closest to \(u^\alpha\), i.e.\(d(w, u^\alpha) \leq d(w, u^\beta)\) for all \(\beta \in \Gamma\). Hence, \(w\) lies in the Dirichlet cell \(D(u^\alpha, u^\Gamma)\). Since \(\alpha\) is an isometry, \(d(w^{\alpha^{-1}}, u) \leq d(w^{\alpha^{-1}}, (u^\beta)^{\alpha^{-1}})\) holds for all \(\beta \in \Gamma\). The above inequality holds for all \(\beta \in \Gamma\) and \(w^{\alpha^{-1}}\) is therefore contained in the Dirichlet cell around \(u\). This means \(w^{\alpha^{-1}} \in D(u, u^\Gamma)\). Since \(w^{\alpha^{-1}}\in v^\Gamma\), we conclude that \(D(u, u^\Gamma)\) contains a representative \(V\) of each orbit of \(\Gamma\) acting on \(\mathbb{R}^n\). It remains to show that \(V\) also contains the interior of \(D(u, u^\Gamma)\). This means that no two points in the interior of \(D(u, u^\Gamma)\) lie in the same orbit of the action of \(\Gamma\) on \(\mathbb{R}^n\). Again, we prove this by contradiction and assume that there exist distinct \(v, w \in \left( D(u, u^\Gamma) \right)^\circ\) and \(\gamma \in \Gamma\) such that \(v^\gamma = w\). The interiors of the Dirichlet cells are pairwise disjoint sets, i.e.\(\left(D(u, u^\Gamma)\right)^\circ\) and \(\left(D(u^\gamma, u^\Gamma)\right)^\circ\) are either disjoint or equal. Since \(\left(D(u^\gamma, u^\Gamma)\right)^\circ = \left( \left(D(u, u^\Gamma)\right)^\circ \right)^\gamma\) and \(v \in \left(D(u^\gamma, u^\Gamma)\right)^\circ\), \(w = v^{\gamma^{-1}} \in \left( \left(D(u, u^\Gamma)\right)^\circ \right)^{\gamma^{-1}}\), the intersection \(D(u,u^\Gamma)^\circ\cap D(u^\gamma,u^\Gamma)^\circ\) is not empty and the Dirichlet cells have to be equal. This implies that \(u = u^\gamma\). Since \(u\) is in general position for \(\Gamma\), this implies \(\gamma = \mathop{\mathrm{Id}}.\) This is a contradiction to \(v \neq w\) and we conclude the proof.

*

First, we recall from [not:cryst-grp-cosets] that \(\Gamma = \bigcup_{i \in I} \rho_i\mathcal{T}(\Gamma)\) holds. This implies \[\mathbb{R}^n = \bigcup_{i \in I}\bigcup_{\tau \in \mathcal{T}(\Gamma)}F^{\rho_i\tau}=\bigcup_{\tau \in \mathcal{T}(\Gamma)} {\left(\bigcup_{i \in I}F^{\rho_i}\right)}^{\tau} =\bigcup_{\tau \in \mathcal{T}(\Gamma)} C^\tau.\] Next, we establish the existence of a system of representatives \(V'\) for the orbits of \(\mathcal{T}(\Gamma)\) acting on \(\mathbb{R}^n\) satisfying \(C^\circ\subseteq V'\subseteq C\). Let therefore \(V\) denote the system of representatives for the orbits of \(\Gamma\) acting on \(\mathbb{R}^n\) with \(F^\circ \subseteq V \subseteq F\). The existence of \(V\) implies \(\bigcup_{i \in I} (F^{\circ})^{\rho_i} \subseteq \bigcup_{i \in I} V^{\rho_i} \subseteq \bigcup_{i \in I} F^{\rho_i} = C\). This allows us to define \(V'\) as \[V' \mathrel{\vcenter{:}}= \bigcup_{i \in I} V^{\rho_i}.\] We claim that \(V'\) is a system of representatives for the orbits of \(\mathcal{T}(\Gamma)\) acting on \(\mathbb{R}^n\). First, we have to show that \(V'\) contains at least one point of each \(\mathcal{T}(\Gamma)\)-orbit. So, let \(x \in \mathbb{R}^n\) be an arbitrary point. Since \(V\) is a system of representatives of the orbits of \(\Gamma\) acting on \(\mathbb{R}^n\), there exist \(z \in V\) and \(\gamma \in \Gamma\) such that \(x = z^\gamma\). Thus, there are \(i \in I\) and \(\tau \in \mathcal{T}(\Gamma)\) such that \(\gamma = \rho_i \tau\). If we define \(y \mathrel{\vcenter{:}}= z^{\rho_i}\), it follows that \(y \in x^{\mathcal{T}(\Gamma)}\). Because of \(y \in V^{\rho_i}\), the statement \(y \in V'\) follows.
Next, we show that \(V'\) contains at most one point of each orbit of \(\mathcal{T}(\Gamma)\) acting on \(\mathbb{R}^n\).

We assume that there are \(x, y \in F^\circ\) with \(x \neq y\) and \(\tau \in \mathcal{T}(\Gamma)\) such that \(x^\tau = y\).

By definition of \(V'\), we know that there exists \(\rho_i\) and \(\rho_j\) such that \(x\in V^{\rho_i}\) and \(y\in V^{\rho_j}.\) Again, since \(V\) is a system of representatives of the action of \(\Gamma\) on \(\mathbb{R}^n\), there exist \(a, b \in F^\circ\) such that \(a^{\rho_i} = x\) and \(b^{\rho_j} = y\). This implies that \(a^{\rho_i \tau \rho_j^{-1}} = x^{\tau \rho_j^{-1}} = y^{\rho_j^{-1}} = b\). Since \(a\) and \(b\) are contained in the fundamental domain \(V\), we get that \(a = b\) and thus \(\rho_i \tau \rho_j^{-1} = Id\). As \(\rho_i \tau = \rho_j\) and \(\{ \rho_i \}_{i \in I}\) are representatives of the cosets this implies that \(i = j\) and therefore \(x = a^{\rho_i} = b^{\rho_j} = y\) which is a contradiction.

References↩︎