Finding equal-diameter tetrahedralizations of polyhedra

Abstract

In this paper we show that every simple polyhedron can be tiled into equal-diameter tetrahedra. Our constructive proof does not give bounds for the number of tetrahedra needed.

1 Introduction

Monsky (1970) proved that the square cannot be tiled by an odd number of equal-area triangles. Bezdek and Bisztriczky (2015) proved that every simple polygon can be partitioned into a finite number of equal-diameter triangles such that the intersection of any two triangles is either empty or consists of a vertex or of an edge.

We generalize this result in three dimensions. A simple polyhedron is a polyhedron whose vertices are adjacent to three edges and three faces. We prove the following

Theorem 1

Every simple polyhedron can be partitioned into a finite number of equal-diameter tetrahedra such that the intersection of any two tetrahedra is either empty or consists of a vertex, of an edge or of a face.

One can find several results on triangulations in the survey paper of Zamfirescu (2013) and in the monograph of De Loera et al. (2010).

2 Notation and terminology

We say that a simple polygon is triangulated if it is partitioned into a finite number of triangles, such that the intersection of any two triangles is either empty or consists of a vertex or of an edge. We say that a set of tetrahedra form a tetrahedralization of a simple polyhedron if it is partitioned into a finite number of tetrahedra, such that the intersection of any two tetrahedra is either empty or consists of a vertex or of an edge or of a face. We say that a triangulation is an $\epsilon$-diameter triangulation if each triangle has a diameter equal to $\epsilon$. We say that a tetrahedralization is an $\epsilon$-diameter tetrahedralization if each tetrahedra has a diameter equal to $\epsilon$.

Throughout this paper, ab will also denote the length of the segment ab. Throughout this paper, $a_1\ldots a_n$ will also denote the convex hull of $a_1\ldots a_n$.

We use the usual notations $\hbox {conv}$ and $\hbox {diam}$ for the convex hull and diameter of a set, respectively. Let $H_1,H_2$ be convex polyhedra and let $H_1{\setminus }H_2$ denote the concave polyhedron subtracting $H_2$ from $H_1$.

3 The proof

We refer remarks and lemmas that can be find in Sect. 3.6. Let $\texttt {P}$ be a simple polyhedron and let $\texttt {P}_1,\ldots ,\texttt {P}_n$ be a partition of $\texttt {P}$ where $\texttt {P}_1, \ldots ,\texttt {P}_n$ are convex polyhedrons and the intersection of any two polyhedrons is either empty or consists of a vertex, of an edge or of a face. In the proof of Bezdek and Bisztriczky (2015) the authors use an acute triangulation of the examined polygon to find an equal-diameter triangulation. If we employ this argument for every face of every small polyhedron $\texttt {P}_1,\ldots ,\texttt {P}_n$ in the same time, then we get an equal-diameter triangulation $\mathcal {T}$ of the faces of the polyhedrons $\texttt {P}_1,\ldots ,\texttt {P}_n$. Observe that the diameters of the triangles on every face are the same.

From now on we examine only one convex polyhedron—say—$\texttt {P}_1$. Let $T_1,\ldots ,T_k$ be the equal-diameter triangulation of the faces of $\texttt {P}_1$ generated by $\mathcal {T}$, where $T_1,\ldots ,T_k$ are the triangles of the triangulation. Let $p_1,\ldots ,p_m$ be the vertices of the triangles ${T}_1,\ldots ,{T}_k$. Let q be a point in the interior of $\texttt {P}_1$ so that $p_1q\not \in \mathbb {N}, \ldots , p_m q\not \in \mathbb {N}$ and let $H_1=\hbox {conv}(T_1,q),\ldots , H_k=\hbox {conv}(T_k,q)$. We show that every tetrahedron $H_i$ can be divide into equal-diameter subtetrahedrons where the intersection of any two subtetrahedrons is either empty or consists of a vertex, of an edge or of a face. Let $\epsilon$ be the diameter of the triangles in $\mathcal {T}$. Let us scale the polyhedron $\texttt {P}$ with the triangles of $\mathcal {T}$, that $\epsilon =1$.

3.1 Extending boundary partitions

Let ABC be a triangle and assume that the boundary of ABC is partitioned by a finite set $S_2$ of vertices including A, B and C. We say that a triangulation of ABC is an extension of the given partition of the boundary if on the boundary of ABC exactly the vertices of $S_2$ are used.

Let ABCD be a tetrahedron and assume that the boundary of ABCD is triangulated by a finite set $S_3$ of triangles. We say that a tetrahedralization of ABCD is an extension of the given triangulation of the boundary if on the boundary of ABCD exactly the triangles of $S_3$ are used.

3.2 Partitioning segments

We partition the segment $p_uq$, $u\in \{1,\ldots ,m\}$ starting with $p_u$ inserting new vertices—say—$p_{u1},\ldots ,p_{un}$, as many as possible, such that they are unit distance apart from each other.

3.3 Partitioning quadrangles

We need the partition only a special type of quadrangle Q which opposite edges have unit length and the rest of the edges have length smaller than or equal to one. We can find the unit-diameter triangulation of Q in Lemma 1 of Bezdek and Bisztriczky (2015) and in Fig. 1.

Fig. 1

Partitioning quadrangles

3.4 Partitioning triangles I

Let $p_jp_iq$ be a face of a tetrahedron $H_u$ and assume that $p_iq\le p_jq$. We call $p_jp_i$ the base of the triangle $p_jp_iq$. We give a triangulation of $p_jp_iq$ that is an extension of the boundary partition of $p_jp_iq$.

Observe $p_ip_j\le 1$. Assume that $0\le n< p_iq<n+1$, thus $n< p_jq<n+2$. Let $p_{i0}=p_{i}$ and $p_{i1}$, $\ldots ,$ $p_{in}$ be the points on $p_iq$ such that $p_ip_{ik} = k$ where $k = 1, \ldots ,n$. We distinguish two cases.

Case 1 We have $n< p_jq<n+1$. Let $p_{j0}=p_{j}$ and $p_{j1}$, $\ldots ,$ $p_{jn}$ be the points on $p_jq$ such that $p_jp_{jk} = k$ for $k = 1, \ldots ,n$ (Fig. 2). Observe $p_ip_{j}>p_{ik}p_{jk}$. Indeed, assume vertex d completes vertices $p_j,p_i,p_{ik}$ to a parallelogram, and notice that the perpendicular bisector of $p_{jk}d$ passes through $p_j$. Since this perpendicular bisector has both $p_{ik}$ and $p_{jk}$ on its same side, we have $p_{ik}p_{jk} < p_{ik}d = p_ip_j$.

Fig. 2

Partitioning triangles I—Case 1

We partition the triangle $p_jp_iq$ into the n quadrangles $p_{j(k-1)}p_{i(k-1)}p_{ik}p_{jk}$ where $k=1,\ldots ,n$ and the triangle $p_{jn}p_{in}q$. By Sect. 3.3 Partitioning quadrangles, the quadrangles have unit-diameter triangulations and the diameter of the triangle $p_{jn}p_{in}q$ is smaller than one.

Case 2 We have $n+1< p_jq<n+2$. Let $p_{j0}=p_{j}$ and $p_{j1}$, $\ldots ,$ $p_{j(n+1)}$ be the points on $p_jq$ such that $p_jp_{jk} = k$ for $k = 1, \ldots , n + 1$ (Fig. 3). We partition the triangle $p_jp_iq$ into the n quadrangles $p_{j(k-1)}p_{i(k-1)}p_{ik}p_{jk}$ where $k=1,\ldots ,n$ and the triangles $p_{jn}p_{in}p_{j(n+1)}$ and $p_{j(n+1)}p_{in}q$. Observe $p_{jn}p_{in}\le 1$ and $p_{in}q<1$. By Remark 1, we have $p_{in}p_{j(n+1)}\le 1$. Thus $\hbox {diam}(p_{jn}p_{in}p_{j(n+1)})=1$ and $\hbox {diam}(p_{j(n+1)}p_{in}q)<1$. By Sect. 3.3, the quadrangles have unit-diameter triangulations.

Fig. 3

Partitioning triangles I—Case 2

3.5 Partitioning triangles II

Let $p_{21}s_2s_1$ be a triangle where $s_1s_2=1$, $p_{21}s_1<2$, and $p_{21}s_2<2$. We give a unit-diameter triangulation of $p_{21}s_2s_1$. If $p_{21}s_1\le 1$ and $p_{21}s_2\le 1$, then the triangle $p_{21}s_2s_1$ is a unit-diameter triangle. We may assume $p_{21}s_1>1$ or $p_{21}s_2>1$. We distinguish three cases.

Fig. 4

Partitioning triangles II—Case 1

Case 1 We have $p_{21}s_1>1$ and $p_{21}s_2\le 1$ (Fig. 4). Let $p_{211}$ be the point on the edge $p_{21}s_1$ such that $p_{21}p_{211}=1$. By Remark 1, $p_{211}s_2\le 1$. The triangles $p_{21}s_2p_{211}$ and $p_{211}s_2s_1$ form a unit-diameter triangulation of the triangle $p_{21}s_2s_1$.

Case 2 We have $p_{21}s_1\le 1$ and $p_{21}s_2>1$. The case is similar to the Case 1 (Fig. 5).

Fig. 5

Partitioning triangles II—Case 2

Case 3 We have $p_{21}s_1>1$ and $p_{21}s_2>1$. Let $p_{211}$ ($p_{212}$, resp.) be the point on the edge $p_{21}s_1$ ($p_{21}s_2$, resp.) such that $p_{211}p_{21}=1$ ($p_{212}p_{21}=1$, resp.).

Let $s_{21}$ be a point in the interior of $p_{211}p_{21}s_2$ such that $s_{21}s_2=1$. We may assume $s_{21}p_{21}\le 1$ and $s_{21}p_{212}\le 1$. We distinguish two subcases.

Fig. 6

Partitioning triangles II—Case 3.1

Subcase 3.1 We have $p_{211}s_2\le 1$ (Fig. 6). By Remark 1, $s_{21}p_{211}\le 1$. Indeed, let $s_{22}$ be the intersection point of the line generated by $s_2, s_{21}$ and the line generated by $p_{211}p_{21}$. Observe, $p_{211}s_{22}<1$.

The triangles $p_{211}s_{2}s_{1}$, $p_{211}p_{21}s_{21}$, $p_{21}p_{212}s_{21}$, $p_{212}s_{2}s_{21}$ and $p_{211}s_{21}s_{2}$ form a unit-diameter triangulation of $p_{21}s_2s_1$.

Fig. 7

Partitioning triangles II—Case 3.2

Subcase 3.2 We have $p_{211}s_2>1$. Let $p_{2112}$ be the point on the edge $p_{211}s_2$ such that $p_{2112}p_{211}=1$ (Fig. 7). The smallest angle in the triangle $p_{21}s_2s_1$ is $s_2p_{21}s_1\angle$ thus $s_2p_{21}s_1\angle <{\pi \over 3}$ and $s_{21}$ lies in the circular sector of center $p_{21}$ through the points $p_{212}$ and $p_{211}$. In this case $p_{211}s_{21}<1$. By Remark 1, $p_{2112}s_{21}\le 1$ and $p_{2112}s_{1}\le 1$. We get the triangles $p_{2112}s_{2}s_{1}$, $p_{211}p_{2112}s_{1}$, $p_{211}p_{21}s_{21}$, $p_{21}p_{212}s_{21}$, $p_{212}s_2s_{21}$, $p_{2112}s_{21}s_{2}$ and $p_{2112}p_{211}s_{21}$ form a unit-diameter triangulation of $p_{21}s_2s_1$.

3.6 Remarks and lemmas

Remark 1

If $a_1a_2a_3$ is a triangle and b is a point on the the side $a_1a_2$, then

$$\begin{aligned} a_3b\le \max \{a_3a_1,a_3a_2\}. \end{aligned}$$

We omit the proof of the remark.

Remark 2

If $a_1a_2a_3a_4$ is a tetrahedron b is a point on the boundary of $a_1a_2a_3a_4$ and c is a point in $a_1a_2a_3a_4$, then

$$\begin{aligned} cb\le \max \{ca_1,ca_2,ca_3,ca_4\}. \end{aligned}$$

Fig. 8

Remark 2

Proof

Firs we assume c lies in the interior of $a_1a_2a_3a_4$. If b is a vertex of $a_1a_2a_3a_4$, then the proof is trivial. Thus we assume that b is not a vertex of $a_1a_2a_3a_4$. We may assume that b lies on the face $a_1a_2a_4$ (Fig. 8). Let $b_1$ be the intersection point of the edge $a_1a_2$ and the plane determined by the points $c, a_4, b$. By Remark 1, $b_1c\le \max \{ca_1,ca_2\}$ and $bc\le \max \{cb_1,ca_4\}$, which completes the proof of the remark if c is an interior point of $a_1a_2a_3a_4$. If c is a boundary point of $a_1a_2a_3a_4$, then the proof is similar. $\square$

Lemma 1

If $a_1a_2a_3a_4$ is a tetrahedron such that $a_1a_2\le 1$, $a_1a_3\le 1$, $a_2a_3\le 1$, $1<a_1a_4\le \alpha$, $a_2a_4\le \alpha$, $a_3a_4\le \alpha$ $(1<\alpha \le 2)$, c is a point in the interior of $a_1a_2a_3a_4$ so that $ca_4=1$ and b is a point on the boundary of $a_1a_2a_3a_4$, then

$$\begin{aligned} bc\le \left\{ \begin{array}{lll} \sqrt{\alpha ^2+1-2\sqrt{\alpha ^2-1}} &{} \hbox { if } &{} \sqrt{2}<\alpha \le 2\\ 1 &{} \hbox { if } &{} 1<\alpha \le \sqrt{2} \end{array}\right. . \end{aligned}$$

Proof

By Remark 2, we need to show that we have

$$\begin{aligned} a_ic<\left\{ \begin{array}{lll} \sqrt{\alpha ^2+1-2\sqrt{\alpha ^2-1}} &{} \hbox { if } &{} \sqrt{2}<\alpha \le 2\\ 1 &{} \hbox { if } &{} 1<\alpha \le \sqrt{2} \end{array}\right. , \quad \hbox {for} \quad \mathrm{i}=1,2,3,4. \end{aligned}$$

Without loss of generality we examine the distance $a_1c$ only. Let $L_0$ be the line determined by the points $a_2$, $a_4$. Let $L_1$ be the line through the point c, perpendicular to the edge $a_1a_4$ and intersecting the line $L_0$ (observe $a_1a_4a_2\angle \ne {\pi \over 2}$). Let $l_{11}$ and $l_{12}$ be the intersecting points of the line $L_1$ and the boundary of $a_1a_2a_3a_4$ such that $d\left( l_{11},L_0\right) \le d\left( l_{12},L_0\right)$. We distinguish two cases.

Case 1 Moving the point c on the line $L_1$ toward the point $l_{11}$ the distance $a_1c$ increases. We distinguish two subcases.

Fig. 9

Lemma 1—Subcase 1.1

Fig. 10

Lemma 1—$\sqrt{2}<\alpha \le 2$

Subcase 1.1 The point $l_{11}$ lies on $a_2a_4$ (Fig. 9). If we move the point c on the line $L_1$ toward the edge $a_2a_4$, then the distances $a_1c$ and $a_4c$ increase. Thus we can assume that c lies on the edge $a_2a_4$. Observe $a_2a_4>1$. If we fix the lengths of $a_1a_4$, $a_2a_4$ and increase the length of $a_1a_2$, then the length of $a_1c$ increases. Thus we may assume that $a_1a_2=1$. If we fix the lengths of $a_1a_2$, $a_2a_4$ and increase the length of $a_1a_4$, then the length of $a_1c$ increases. Thus we may assume that $a_1a_4=\alpha$. Let $C_1$ be the circle of radius $\alpha$ and center $a_1$. Let $C_2$ be the circle through the three points $a_1,a_2$ and $a_4$. We fix the points $a_1$ and $a_2$, and we move $a_4$ on the circle $C_1$. Let $\mathcal {H}$ be the halfplane bounded by the line through the points $a_1$, $a_2$ and containing $a_4$. Let R be the ray through the point $a_2$ and perpendicular to the segment $a_1a_2$ in the halfplane $\mathcal {H}$. Let $r_1$ be the intersection point of $C_1$ and R (Fig. 10). Let $r_2$ be the point on the circle $C_1$ in the halfplane $\mathcal {H}$ such that $a_2r_2=1$ (Fig. 11). Since the length of the edges $a_1a_4$ and $a_4c$ are fix, the length of $a_1c$ is the greatest if the angle $a_1a_4c\angle$ is the greatest, that is, if $a_4=r_1$ if $\sqrt{2}<\alpha \le 2$ (in this case $C_1$ and $C_2$ touch each other) and $r_2$ if $1<\alpha \le \sqrt{2}$ (in this case the radius of $C_2$ is the smallest). Thus $a_1c\le \sqrt{\alpha ^2+1-2\sqrt{\alpha ^2-1}}$ if $\sqrt{2}<\alpha \le 2$ and $a_1c\le 1$ if $1<\alpha \le \sqrt{2}$, which completes the proof of the subcase.

Fig. 11

Lemma 1—$1<\alpha \le \sqrt{2}$

Subcase 1.2 The point $l_{11}$ lies on the face $a_1a_2a_3$. Since the diameter of the triangle $a_1a_2a_3$ is one, we have $1>a_1l_{11}>a_1c$.

Case 2 Moving the point c on the line $L_1$ toward the point $l_{12}$ the distance $a_1c$ increases. Observe $l_{12}$ lies in the relative interior of the face $a_1a_3a_4$. Let $R_3$ be the ray starting at $l_{12}$, perpendicular to the edge $a_1a_4$ and lying in the halfplane determined by the line trough the points $a_1$, $a_4$ and containing the point $a_3$. Let $r_3$ be the intersection point of $R_3$ and the relative boundary of the face $a_1a_3a_4$. Observe $a_1c\le a_1l_{12}\le a_1r_3$ and $a_4c\le a_4l_{12}\le a_4r_3$. We distinguish two subcases.

Subcase 2.1 The point $r_3$ lies on $a_3a_4$. The proof is similar to the proof of Subcase 1.1.

Subcase 2.2 The point $r_3$ lies on $a_1a_3$. The proof is similar to the proof of Subcase 1.2.

This completes the proof of the lemma. $\square$

Lemma 2

If $p_{11}p_{21}qs_1$ is a tetrahedron such that the diameter of $p_{11}p_{21}q$ is not greater than one and $s_1q=1$, then $p_{11}p_{21}qs_1$ has unit-diameter tetrahedralization.

Proof

If $p_{11}s_1\le 1$ and $p_{21}s_1\le 1$, then $\hbox {diam}(p_{11}p_{21}qs_1)=1$. Thus we may assume $p_{11}s_1>1$. Let $p_{111}$ be the point on $p_{11}s_1$ such that $p_{11}p_{111}=1$. We use the triangulations of the faces $p_{11}qs_1$, $p_{21}qs_1$ and $p_{11}p_{21}s_1$ generated by Sect. 3.4 and we extend this boundary partition to a unit-diameter tetrahedralization. We distinguish two cases.

Case 1 We have $p_{21}s_1\le 1$ (Fig. 12). By Remark 1, $p_{111}q\le 1$ and $p_{111}p_{21}\le 1$. The tetrahedra $p_{11}p_{21}p_{111}q$ and $p_{21}p_{111}qs_1$ form a unit-diameter tetrahedralization of $p_{11}p_{21}qs_1$.

Fig. 12

Lemma 2—Case 1

Fig. 13

Lemma 2—Case 2

Case 2 We have $p_{21}s_1>1$. Let $p_{211}$ be the point on $p_{21}s_1$ such that $p_{21}p_{211}=1$ (Fig. 13). Let $T^1,\ldots ,T^7$ be the triangles of the triangulation of $p_{11}p_{21}s_1$ generated by Sect. 3.4. By Remark 2, $pq\le 1$ where p is a vertex of $T^1$ or $\ldots$ or $T^7$. The tetrahedra $\hbox {conv}(T^1,q)$, $\ldots$, $\hbox {conv}(T^7,q)$ form a unit-diameter tetrahedralization of $p_{11}p_{21}qs_1$. This completes the proof of the lemma. $\square$

Lemma 3

If $p_{1}p_{2}p_3q$ is a tetrahedron such that the diameter of $p_1p_2p_3$ is one, $p_1q<2$, $p_2q<2$ and $p_3q<2$, then $p_{1}p_{2}p_3q$ has unit-diameter tetrahedralization.

Proof

Let ${\mathcal A}=\{p_1q,p_2q,p_3q\}$. If $p_1q\le 1$, $p_2q\le 1$ and $p_3q\le 1$, then $\hbox {diam}(p_{1}p_{2}p_3q)=1$. Thus we may assume there is a length in ${\mathcal A}$ that is greater than one. First we create a tetrahedralization where the diameters of the tetrahedra are not greater than $\sqrt{5-2\sqrt{3}}=1.239\ldots$, next we create one where the diameters of the tetrahedra are exactly one. We use the triangulations of the faces $p_1p_2q$, $p_1p_3q$ and $p_2p_3q$ generated by Sect. 3.4 and we extend this boundary partition to a unit-diameter tetrahedralization. We refer the points $p_{11}$, $p_{21}$ and $p_{31}$ (if there exist) generated by Sect. 3.4. Let $s_{1}$ be a point in the interior of $p_1p_2p_3q$ such that $s_{1}q=1$. We distinguish three cases.

Fig. 14

Lemma 3—Case 1

Case 1 There is a unique length in the set ${\mathcal {A}}$ which is greater than one. We assume $p_1q\le 1$, $p_2q\le 1$ and $1<p_3q$. (The cases ($p_1q\le 1$, $1<p_2q$, $p_3q\le 1$) and ($1<p_1q$, $p_2q\le 1$, $p_3q\le 1$) are similar.) We can choose the position of $s_1$ such that $p_3s_1<1$ and $p_{31}s_1<1$ (Fig. 14). By Remark 1, $p_1s_1<1$ and $p_2s_1<1$ (because of $\hbox {diam}(p_1p_2p_3)=1$). Thus the tetrahedra $p_1p_2p_3s_{1}$, $p_2p_3p_{31}s_{1}$, $p_2p_{31}qs_{1}$, $p_1p_3p_{31}s_{1}$, $p_1p_{31}qs_{1}$ and $p_1p_{2}qs_{1}$ form a unit-diameter tetrahedralization of $p_1p_2p_3q$.

Fig. 15

Lemma 3—Case 2

Case 2 There are exactly two lengths in the set ${\mathcal {A}}$ which are greater than one. We assume that $1<p_1q$, $1<p_2q$ and $p_3q\le 1$ (Fig. 15). (The cases ($1<p_1q$, $p_2q\le 1$ and $1<p_3q$) and ($p_1q\le 1$, $1<p_2q$ and $1<p_3q$) are similar.) Let $T^1=p_{11}p_{21}q,T^2=p_{21}p_{3}q,T^3=p_{11}p_{3}q,T^4,\ldots ,T^{11}$ be the triangles of the triangulations of the faces $p_1p_2q$, $p_1p_3q$ and $p_2p_3q$ generated by Sect. 3.4 and $T^{12}=p_1p_2p_3$. Let $H^i=\hbox {conv}\left( T_1^i,s_{1}\right)$ for $i=1,2,\ldots ,12$. By Lemma 1 $(\alpha =2)$, each tetrahedron $H^i$ $(i=4,\ldots ,12)$ has a unit-diameter base and every other edges have length not greater then $\sqrt{5-2\sqrt{3}}=1.239\ldots$ By Lemma 2, the tetrahedra $H^1,H^2,H^3$ have unit-diameter tetrahedralization. Thus we created a tetrahedralization where the diameters of the tetrahedra are not smaller than one and not greater than $\sqrt{5-2\sqrt{3}}=1.239\ldots$

We examine the tetrahedron $H^i$. Let $p'_1p'_2p'_3$ be the vertices of $T^i$ (the base of $H^i$) and $s_{1}$ be the apex of $H^i$. Let ${\mathcal A'}=\{p'_1s_1,p'_2s_1,p'_3s_1\}$. If $p'_1s_1\le 1$, $p'_2s_1\le 1$ and $p'_3s_1\le 1$, then $\hbox {diam}(p'_1p'_2p'_3s_1)=1$. Thus we may assume there is a length in ${\mathcal A'}$ that is greater than one. We use the triangulations of the faces $p'_1p'_2s_1$, $p'_1p'_3s_1$ and $p'_2p'_3s_1$ generated by Sect. 3.4 (with bases $p'_1p'_2$, $p'_1p'_3$ and $p'_2p'_3$) and we extend this boundary partition to a unit-diameter tetrahedralization. We refer the points $p'_{11}$, $p'_{21}$ and $p'_{31}$ (if there exist) generated by Sect. 3.4. Let $s'_{1}$ be a point in the interior of $p'_1p'_2p'_3s_1$ such that $s'_{1}s_1=1$. We distinguish three subcases.

Subcase 2.1 There is a unique length in the set ${\mathcal {A}'}$ which is greater than one. The proof is similar to the proof of Case 1.

Subcase 2.2 There are exactly two lengths in the set ${\mathcal {A}'}$ which are greater than one. We assume that $1<p'_1s_1$, $1<p'_2s_1$ and $p'_3s_1\le 1$ (Fig. 16). (The subcases ($1<p'_1s_1$, $p'_2s_1\le 1$ and $1<p'_3s_1$) and ($p'_1s_1\le 1$, $1<p'_2s_1$ and $1<p'_3s_1$) are similar.) Let ${T'}^1=p'_{11}p'_{21}s_{1},{T'}^2=p'_{21}p'_{3}s_{1},{T'}^3=p'_{11}p'_{3}s_{1},{T'}^4,\ldots ,{T'}^{11}$ be the triangles of the triangulations of the faces $p'_1p'_2s_1$, $p'_1p'_3s_1$ and $p'_2p'_3s_1$ generated by Sect. 3.4, with bases $p'_1p'_2$, $p'_1p'_3$, $p'_2p'_3$ and let ${T'}^{12}={p'}_1{p'}_2{p'}_3$. Observe ${T'}^4,\ldots ,{T'}^{12}$ are unit diameter triangles. Let ${H'}^i=\hbox {conv}({T'}^i,s'_{1})$ for $i=1,\ldots ,12$. By Lemma 1 $(\alpha =\sqrt{5-2\sqrt{3}}=1.239\ldots )$, we have $ps'_{1}\le 1$ where p is a vertex of ${T'}^1$ or $\ldots$ or ${T'}^{12}$, that is, the diameter of ${H'}^i$ is one for $i=1,\ldots ,12$. The tetrahedra ${H'}^1,\ldots ,{H'}^{12}$ form a unit-diameter tetrahedralization of ${p'}_1{p'}_2{p'}_3s_1$.

Fig. 16

Lemma 3—Subcase 2.2

Fig. 17

Lemma 3—Subcase 2.3

Subcase 2.3 We have $1<p'_1s_1$, $1<p'_2s_1$ and $1<p'_3s_1$. Let ${T'}^1=p'_{11}p'_{21}s_{1},{T'}^2=p'_{21}p'_{31}s_{1},{T'}^3=p'_{11}p'_{31}s_{21},{T'}^4,\ldots ,{T'}^{21}$ be the triangles of the triangulations of the faces $p'_1p'_2s_1$, $p'_1p'_3s_1$ and $p'_2p'_3s_1$ generated by Sect. 3.4 with bases $p'_1p'_2$, $p'_1p'_3$, $p'_2p'_3$ and let ${T'}^{22}={p'}_1{p'}_2{p'}_3$ (Fig. 17). Let ${H'}^i=\hbox {conv}({T'}^i,s'_{1})$ for $i=1,\ldots ,22$. By Lemma 1 $(\alpha =\sqrt{5-2\sqrt{3}}=1.239\ldots )$, we have $ps'_{1}\le 1$ where p is a vertex of ${T'}^1$ or $\ldots$ or ${T'}^{22}$, that is, the diameter of ${H'}^i$ is unit for $i=1,\ldots ,22$. The tetrahedra ${H'}^1,\ldots ,{H'}^{22}$ form a unit-diameter tetrahedralization of ${p'}_1{p'}_2{p'}_3s_1$.

Observe the intersection of any two subtetrahedrons is either empty or consists of a vertex, of an edge or of a face, which completes the proof of the Case 2.

Case 3 We have $1<p_1q$, $1<p_2q$ and $1<p_3q$. Let $T^1=p_{11}p_{21}q, T^2=p_{21}p_{31}q,T^3=p_{11}p_{31}q,T^4,\ldots ,T^{21}$ be the triangles of the triangulations of the faces $p_1p_2s_1$, $p_1p_3s_1$ and $p_2p_3s_1$ generated by Sect. 3.4 and let $T^{22}=p_1p_2p_3$ (Fig. 18). Let $H^i=\hbox {conv}\left( T^i,s_1\right)$ for $i=1,\ldots ,22$. By Lemma 1, each tetrahedron $H^i$ $(i=4,\ldots ,22)$ has unit-diameter base and every other edges have length not greater then $\sqrt{5-2\sqrt{3}}=1.239\ldots$ By Lemma 2, the tetrahedra $H^1,H^2,H^3$ have unit-diameter tetrahedralization. Thus we get a tetrahedralization where the diameters of the tetrahedra are not smaller than one and not greater than $\sqrt{5-2\sqrt{3}}=1.239\ldots$ We examine the tetrahedron $H^i$. Let $p'_1p'_2p'_3$ be the vertices of $T^i$ (the base of $H^i$) and $s_{1}$ be the apex of $H^i$. The proof is similar to the proof of Subcases 2.1, 2.2 and 2.3.

Observe the intersection of any two subtetrahedra is either empty or consists of a vertex, of an edge or of a face, which completes the proof of the lemma. $\square$

Corollary 1

If $p_{1}p_{2}p_3q$ is a tetrahedron such that $\hbox {diam}(p_1p_2p_3)=1$, $p_1q<2$, $p_2q<2$, $p_3q<2$, $\hbox {diam}(p_1p_2p_3q)>1$ and let $s_{1}$ be a point in the interior of $p_1p_2p_3q$ such that $s_{1}q=1$, then the concave polyhedron $p_{1}p_{2}p_3q{\setminus } p_{1}p_{2}p_3s_1$ has unit-diameter tetrahedralization.

Proof

The proof comes from the proof of Lemma 3. $\square$

Fig. 18

Lemma 3—Case 3

Lemma 4

If $p_{21}p_{31}s_1s_2$ is a tetrahedron such that $s_1s_2=1$, $p_{21}s_1<2$, $p_{31}s_1<2$, $p_{21}s_2<2$, $p_{31}s_2<2$ and $p_{21}p_{31}\le 1$, then $p_{21}p_{31}s_1s_2$ has unit-diameter tetrahedralization.

Proof

Let ${\mathcal B}=\{p_{21}s_1,p_{31}s_1,p_{21}s_2,p_{31}s_2\}$. If $p_{21}s_1\le 1$, $p_{31}s_1\le 1$, $p_{21}s_2\le 1$ and $p_{31}s_2\le 1$, then $p_{21}p_{31}s_1s_2$ is a unit-diameter tetrahedron. Thus we may assume there is a length in the set ${\mathcal B}$ which is greater than one. Without loss of generality we can assume $p_{21}s_1>1$. If $p_{i1}s_k>1$, then let $p_{i1k}$ be the point on the edge $p_{i1}s_k$ such that $p_{i1}p_{i1k}=1$ for $i=2,3$, $k=1,2$. We use the triangulation of the faces $p_{21}s_1s_2$ and $p_{31}s_1s_2$ generated by Sect. 3.5; and the triangulations of the faces $p_{21}p_{31}s_1$ and $p_{21}p_{31}s_2$ generated by Sect. 3.4. We extend these boundary triangulation to a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$. Observe $\hbox {diam}(p_{21}p_{31}s_1s_2)<2$ thus the distance of any two points in $p_{21}p_{31}s_1s_2$ is smaller than two. We distinguish four cases.

Fig. 19

Lemma 4—Case 1

Case 1 There is a unique length in the set ${\mathcal {B}}$ which is greater than one (Fig. 19). The tetrahedra $p_{21}p_{31}p_{211}s_2$ and $p_{211}p_{31}s_1s_2$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Case 2 There are exactly two lengths in the set ${\mathcal {B}}$ which is greater than one. We distinguish three subcases.

Fig. 20

Lemma 4—Case 2.1

Subcase 2.1 We have $p_{31}s_2>1$ (Fig. 20). Let $T^1=p_{21}p_{31}p_{211}$, $T^2=p_{211}p_{31}s_1$ be the triangles of the triangulation of $p_{21}p_{31}s_1$ generated by Sect. 3.4. Let $T^3=p_{21}p_{31}p_{312}$, $T^4=p_{21}p_{312}s_2$ be the triangles of the triangulation of $p_{21}p_{31}s_2$ generated by Sect. 3.4. Let $T^5=p_{211}p_{21}s_{2}$, $T^6=p_{211}s_{2}s_1$ be the triangles of the triangulation of $p_{21}s_{2}s_{1}$ generated by Sect. 3.5. Let $T^7=p_{31}p_{312}s_{1}$, $T^8=p_{312}s_{2}s_1$ be the triangles of the triangulation of $p_{31}s_{2}s_{1}$ generated by Sect. 3.5. By Remark 1, $p_{211}p_{312}\le 1$. Let $s_{21}$ be a point in the interior of $p_{21}p_{31}p_{211}s_2$ such that $s_{21}s_2=1$. By Lemma 3, the tetrahedra $\hbox {conv}(T^1,s_{21})$, $\hbox {conv}(T^3,s_{21})$, $\hbox {conv}(T^5,s_{21})$, $p_{31}p_{312}p_{211}s_{21}$ have unit-diameter tetrahedralization, by Lemma 2, $\hbox {conv}(T^4,s_{21})$, $p_{211}p_{312}s_{2}s_{21}$ have unit-diameter tetrahedralization. These subtetrahedra, $p_{211}p_{31}s_1p_{312}$ and $p_{211}p_{312}s_1s_2$ form a unit-diameter tetrahedralization of the examined tetrahedron $p_{21}p_{31}s_1s_2$.

Subcase 2.2 We have $p_{21}s_2>1$. Let $s_{21}$ be a point in the interior of $p_{21}p_{31}p_{211}s_2$ such that $s_{21}s_2=1$. Let $T^1=p_{21}p_{31}p_{211}$, $T^2=p_{211}p_{31}s_1$ be the triangles of the triangulation of $p_{21}p_{31}s_1$ generated by Sect. 3.4. Let $T^3=p_{21}p_{31}p_{212}$, $T^4=p_{212}p_{31}s_2$ be the triangles of the triangulation of $p_{21}p_{31}s_2$ generated by Sect. 3.4 and let $T^{5}=p_{31}s_{2}s_{1}$. We distinguish two subcases.

Fig. 21

Lemma 4—Case 2.2.1

Subcase 2.2.1 We have $p_{211}s_2\le 1$ (Fig. 21). Let $T^6=p_{211}s_{2}s_1$, $T^7$, $\ldots$, $T^{10}$ be the triangles of the unit-diameter triangulation of $p_{21}s_{2}s_{1}$ generated by Sect. 3.5 and $T^{11}=p_{211}p_{31}s_2$. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=1,\ldots ,11$, $i\ne 2,i\ne 4,i\ne 5,i\ne 6$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^4,s_{21})$ and $\hbox {conv}(T^{11},s_{21})$ have unit-diameter tetrahedralization. These subtetrahedra and $p_{211}p_{31}s_1s_2$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Fig. 22

Lemma 4—Case 2.2.2

Subcase 2.2.2 We have $p_{211}s_2>1$. Let $p_{2112}$ be the point generated by Sect. 3.5 (Fig. 22). Let $T^6=p_{211}p_{2112}s_1$, $T^7=p_{2112}s_2s_1$, $T^8$, $\ldots$, $T^{12}$ be the triangles of the unit-diameter triangulation of $p_{21}s_{2}s_{1}$ generated by Sect. 3.5. Let $T^{13}=p_{211}p_{31}p_{2112}$, $T^{14}=p_{2112}p_{31}s_2$ be the triangles of the triangulation of $p_{211}p_{31}s_2$ generated by Sect. 3.4. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=1,\ldots ,13$, $i\ne 2,i\ne 4,i\ne 5,i\ne 6,i\ne 7$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^4,s_{21})$ and $\hbox {conv}(T^{14},s_{21})$ have unit-diameter tetrahedralization. These subtetrahedra $\hbox {conv}(T^{13},s_{1})$ and $\hbox {conv}(T^{14},s_{1})$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Fig. 23

Lemma 4—Case 2.3

Subcase 2.3 We have $p_{31}s_1>1$ (Fig. 23). Let $T^1,\ldots ,T^7$ be the triangles of the triangulation of $p_{21}p_{31}s_1$ generated by Sect. 3.4. Observe $ps_2\le 1$ where p is a vertex of $T^1$ or $\ldots$ or $T^7$. The tetrahedra $\hbox {conv}(T^1,s_2),\ldots ,\hbox {conv}(T^7,s_2)$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Case 3 There are exactly three lengths in the set ${\mathcal {B}}$ which are greater than one. Let $s_{21}$ be a point in the interior of $p_{21}p_{31}p_{211}s_2$ such that $s_{21}s_2=1$. We distinguish three subcases.

Subcase 3.1 We have $p_{31}s_1>1$ and $p_{21}s_2 >1$. Let $T^{1} = p_{211}p_{311}s_1, T^{2},\ldots$, $T^{7}$ be the triangles of the triangulation of $p_{21}p_{31}s_1$ generated by Sect. 3.4. Let $T^{8}, T^{9}=p_{212}p_{31}s_2$ be the triangles of the triangulation of $p_{21}p_{31}s_2$ generated by Sect. 3.4. Let $T^{10}=p_{311}s_2s_1,T^{11}$ be the triangles of the unit-diameter triangulation of $p_{31}s_{2}s_1$ generated by 3.5 Partitioning triangles II. Observe, that $T^i$ for $i=2,\ldots ,8,10,11$ are unit-diameter triangles and the diameters of $T^{1}$ and $T^9$ are not greater than one. We distinguish two subcases.

Fig. 24

Lemma 4—Case 3.1.1

Subcase 3.1.1 We have $p_{211}s_2\le 1$ (Fig. 24). Let $T^{12}=p_{211}s_2s_1,T^{13},\ldots ,$ $T^{16}$ be the triangles of the unit-diameter triangulation of $p_{21}s_2s_1$ generated by Sect. 3.5 Partitioning triangles II. Let $T^{17}=p_{211}p_{311}s_2$. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=2,\ldots ,16$, $i\ne 9,i\ne 10,i\ne 12$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=9,17$ have unit-diameter tetrahedralization. These subtetrahedra and $\hbox {conv}(T^{17},s_{1})$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Fig. 25

Lemma 4—Case 3.1.2

Subcase 3.1.2 We have $p_{211}s_2>1$. Let $p_{2112}$ be the point generated by Sect. 3.5 (Fig. 25). Let $T^{12}=p_{211}p_{2112}s_1$, $T^{13}=p_{2112}s_2s_1$, $T^{14},\ldots ,T^{18}$ be the triangles of the unit-diameter triangulation of $p_{21}s_2s_1$ generated by Sect. 3.5. Let $T^{19}=p_{211}p_{311}p_{2112}$ and $T^{20}=p_{311}p_{2112}s_2$. By Remark 1, $p_{311}p_{2112}\le 1$. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=2,\ldots ,19$, $i \!\ne \!9,i\!\ne \!10,i\ne 12,i\ne 13$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=9,20$ have unit-diameter tetrahedralization. These subtetrahedra, $\hbox {conv}(T^{19},s_{1})$ and $\hbox {conv}(T^{20},s_{1})$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Subcase 3.2 We have $p_{31}s_1>1$ and $p_{31}s_2>1$. The proof is similar to the proof of Subcase 3.1 (Fig. 26).

Fig. 26

Lemma 4—Subcase 3.2

Subcase 3.3 We have $p_{21}s_2>1$ and $p_{31}s_2>1$. Let $T^1=p_{211}p_{31}s_1,T^2$ be the triangles of the triangulation of $p_{21}p_{31}s_1$ generated by Sect. 3.4. Let $T^3=p_{212}p_{312}s_2,T^4,\ldots ,T^{9}$ be the triangles of the triangulation of $p_{21}p_{31}s_2$ generated by Sect. 3.4. Let $T^{10}$, $T^{11}$ be the triangles of the triangulation of $p_{31}s_{2}s_1$ generated by Sect. 3.5. We distinguish two subcases.

Fig. 27

Lemma 4—Subcase 3.3.1

Subcase 3.3.1 We have $p_{211}s_2\le 1$ (Fig. 27). Let $T^{12}\!=\!p_{211}s_{2}s_1$, $T^{13}$, $\ldots$, $T^{16}$ be the triangles of the triangulation of $p_{21}s_{2}s_1$ generated by Sect. 3.5. Let $T^{17}=p_{211}p_{312}s_2$, $T^{18}=p_{211}p_{31}p_{312}$. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i = 2,\ldots ,18$, $i \ne 3,i\ne 10,i\ne 11,i\ne 12,i\ne 17$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=3,17$ have unit-diameter tetrahedralization. These subtetrahedra, $\hbox {conv}(T^{17},s_{1})$ and $\hbox {conv}(T^{18},s_{1})$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Fig. 28

Lemma 4—Subcase 3.3.2

Subcase 3.3.2 We have $p_{211}s_2>1$. Let $p_{2112}$ be the point generated by Sect. 3.5 (Fig. 28). Let $T^{12}=p_{211}p_{2112}s_1$, $T^{13}=p_{2112}s_2s_1$, $T^{14}$, $\ldots$, $T^{18}$ be the triangles of the triangulation of $p_{21}s_{2}s_1$ generated by Sect. 3.5. Let $T^{19}=p_{2112}p_{312}s_2,T^{20},\ldots ,T^{25}$ be the triangles of the triangulation of $p_{211}p_{31}s_2$ generated by Sect. 3.4. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i = 2,\ldots ,25$, $i\ne 3,i \ne 10$, $i \ne 11,i\ne 12,i\ne 13,i\ne 19$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=3,19$ have unit-diameter tetrahedralization. These subtetrahedra and $\hbox {conv}(T^i,s_{1})$ for $i= 19,\ldots ,25$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Case 4 All the elements in the set ${\mathcal {B}}$ are greater than one. Let $T^{1}=p_{211}p_{311}s_1,T^{2},\ldots ,T^{7}$ be the triangles of the triangulation of $p_{21}p_{31}s_1$ generated by Sect. 3.4. Let $T^{8}=p_{212}p_{312}s_2,T^{9},\ldots ,T^{14}$ be the triangles of the triangulation of $p_{21}p_{31}s_2$ generated by Sect. 3.4. Observe, that $T^i$ for $i=2,\ldots ,14$, $i\ne 8$ are unit-diameter triangles and the diameters of $T^{1}$ and $T^{8}$ are smaller than one. We distinguish four subcases.

Fig. 29

Lemma 4—Subcase 4.1

Subcase 4.1 We have $p_{211}s_2\le 1$ and $p_{311}s_2\le 1$ (Fig. 29). Let $T^{15}=p_{211}s_2s_1,T^{16},\ldots ,T^{19}$ be the triangles of the unit-diameter triangulation of $p_{21}s_2s_1$ generated by Sect. 3.5. Let $T^{20}=p_{311}s_2s_1,T^{21},\ldots ,$ $T^{24}$ be the triangles of the unit-diameter triangulation of $p_{31}s_2s_1$ generated by Sect. 3.5 Partitioning triangles II. Let $T^{25}=p_{211}p_{311}s_2$. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=2,\ldots ,24$, $i\ne 8,i\ne 15, i\ne 20$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^8,s_{21})$ and $\hbox {conv}(T^{25},s_{21})$ have unit-diameter tetrahedralization. These subtetrahedra and $\hbox {conv}(T^{25},s_{1})$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Fig. 30

Lemma 4—Subcase 4.2

Subcase 4.2 We have $p_{211}s_2>1$ and $p_{311}s_2\le 1$. Let $p_{2112}$ be the point generated by Sect. 3.5 (Fig. 30). By Remark 1, $p_{311}p_{2112}\le 1$. Let $T^{15}=p_{211}p_{2112}s_1,T^{16}=p_{2112}s_2s_1,T^{16},\ldots ,T^{21}$ be the triangles of the unit-diameter triangulation of $p_{21}s_2s_1$ generated by Sect. 3.5. Let $T^{22}=p_{311}s_2s_1,T^{23},\ldots ,T^{26}$ be the triangles of the unit-diameter triangulation of $p_{31}s_2s_1$ generated by Sect. 3.5. Let $T^{27}=p_{211}p_{311}p_{2112}$ and $T^{28}=p_{2112}p_{311}s_2$. By Lemma 3, the tetrahedra $\hbox {conv}(T^i,s_{21})$ for $i=2,\ldots ,27$, $i\ne 8,i\ne 15,i\ne 16,i\ne 22$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedra $\hbox {conv}(T^8,s_{21})$ and $\hbox {conv}(T^{28},s_{21})$ have unit-diameter tetrahedralization. These subtetrahedra, $\hbox {conv}(T^{27},s_{1})$ and $\hbox {conv}(T^{28},s_{1})$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$.

Subcase 4.3 We have $p_{211}s_2\le 1$ and $p_{311}s_2>1$. The proof is similar to the proof of Subcase 4.2.

Fig. 31

Lemma 4—Subcase 4.4

Subcase 4.4 We have $p_{211}s_2>1$ and $p_{311}s_2>1$. Let $p_{2112}$ and $p_{3112}$ be the points generated by Sect. 3.5 (Fig. 31). Let $T^{15}=p_{211}p_{2112}s_1, T^{16}=p_{2112}s_2s_1,T^{17}\ldots ,T^{21}$ be the triangles of the unit-diameter triangulation of $p_{21}s_2s_1$ generated by Sect. 3.5. Let $T^{22}=p_{311}p_{3112}s_1,T^{23}=p_{3112}s_2s_1,T^{24},\ldots ,T^{28}$ be the triangles of the unit-diameter triangulation of $p_{31}s_2s_1$ generated by Sect. 3.5. Let $T^{29}=p_{2112}p_{3112}s_2,T^{30},\ldots ,T^{35}$ be the triangles of the triangulation of $p_{211}p_{311}s_2$ generated by Sect. 3.4. By Lemma 3, $\hbox {conv}(T^i,s_{21})$ for $i=2,\ldots ,35$, $i\ne 8,i\ne 15,i\ne 16,i\ne 22,i\ne 23,i\ne 29$ have unit-diameter tetrahedralization. By Lemma 2, the tetrahedron $\hbox {conv}(T^8,s_{21})$ and $\hbox {conv}(T^{29},s_{21})$ have unit-diameter tetrahedralization. These subtetrahedra and $\hbox {conv}(T^i,s_{1})$ for $i=29,\ldots ,35$ form a unit-diameter tetrahedralization of $p_{21}p_{31}s_1s_2$ which completes the proof of the lemma. $\square$

3.7 The unit-diameter tetrahedralization of the tetrahedra $H_i$

Without loss of generality we examine the tetrahedron $H_1=\hbox {conv}(T_1,q)$. Let us assume that the vertices of $T_1$ are $p_1$, $p_2$ and $p_3$. Observe $p_1p_2 \le 1,p_2p_3\le 1$,$p_1p_3 \le 1$ and at least one equality holds true. Let ${\mathcal A}=\{p_1q,p_2q,p_3q\}$ and we may assume that $p_1q\le p_2q\le p_3q$. We distinguish two cases.

Case 1 We have $p_3q<2$. Observe $p_1q<2,p_2q<2,p_3q<2$. The proof comes from Lemma 3.

Fig. 32

The unit-diameter tetrahedralization—Case 2

Case 2 We have $2<p_3q$. We assume, that $2\le n<p_3q< n+1$. Thus $n-1<p_1q<n+1$ and $n-1<p_2q<n+1$. Let $p_{11},\ldots , p_{1n}, p_{21},\ldots ,p_{2n}, p_{31},\ldots$, $p_{3n}$ be the vertices on the edges $p_1q$, $p_2q$, $p_3q$ generated by Sect. 3.2 (maybe the points $p_{1n}$, $p_{2n}$ do not exist). Let $p_{10}=p_1,p_{20}=p_2,p_{30}=p_3$ (Fig. 32). We extended these vertices to a triangulation of the boundary of $H_1$, then we extended these triangulation to a unit-diameter tetrahedralization of $H_1$. Let $s_0$ be a point on the face $p_1p_2p_3$. If $s_0p_3$ sufficiently small, then $s_0q>n$. Let $s_i$ be the point on $s_0q$ such that $qs_i=n+1-i$ for $i=1,\ldots , n$. We can choose the position of $s_0$ so that $p_{ij}s_k\ne 2$ for $i=1,2,3$, $j=0,\ldots ,n$ and $k=1,\ldots ,n$ thus we assume that $p_{ij}s_k\ne 2$ for $i=1,2,3$, $j=0,\ldots ,n$ and $k=1,\ldots ,n$. If $s_0p_3$ sufficiently small, then $s_i$ lies in $\hbox {conv}\left( p_{(i-1)1},p_{(i-1)2},p_{(i-1)3},p_{i1},p_{i2},p_{i3}\right)$ for $i=1,\ldots ,n$. We partition $p_1p_2p_3q$ into four sets of polyhedra $S_1,S_2,S_3,S_4$. The sets are the following:

$S_1=\{p_1p_2p_3s_1\}$ (Fig. 33),

$S_2=\{p_{i1}p_{i2}p_{(i+1)2}p_{(i+1)1}s_{i+1}, p_{i1}p_{i3}p_{(i+1)3}p_{(i+1)1}s_{i+1} ,p_{i2}p_{i3}p_{(i+1)3}p_{(i+1)2}s_{i+1} \hbox {for }i=0,\ldots ,n-2\}$ (Fig. 34),

$S_3=\{p_{1i}p_{2i}s_{i}s_{i+1},p_{1i}p_{3i}s_{i}s_{i+1},p_{2i}p_{3i}s_{i}s_{i+1}\hbox { for }i=1,\ldots ,n-1\}$ (Fig. 35),

$S_4=\{p_{1(n-1)}p_{2(n-1)}p_{3(n-1)}q{\setminus } p_{1(n-1)}p_{2(n-1)}p_{3(n-1)}s_n\}$.

Fig. 33

The unique element of $S_1$: the tetrahedron $p_{1}p_{2}p_{3}s_{1}$

Fig. 34

An element of $S_2$: the pyramid with base $p_{1}p_{2}p_{21}p_{11}$ and apex $s_1$

Fig. 35

An element of $S_3$: the tetrahedron $p_{21}p_{31}s_{1}s_{2}$

The unique element of the set $S_1$ is a unit-diameter tetrahedron.

Now we examine the elements of the set $S_2$. Without loss of generality we examine the element $p_1p_2p_{21}p_{11}s_1$ only.

We have $p_{ij}s_1<2$ for $i=1,2$ and $j=0,1$. Indeed, the lengths of the edges and the diagonals of $p_1p_2p_3p_{11}p_{21}p_{31}$ are smaller than two, that is, $\hbox {diam}(p_1p_2p_{21}p_{11}s_1)\!<\!2$.

Let $T^1,\ldots ,T^6$ be the triangles of the unit-diameter triangulation of the quadrangle $p_1p_2p_{21}p_{11}$ generated by Sect. 3.3. By Lemma 3, $\hbox {conv}(T^1,s_1),\ldots ,\hbox {conv}(T^6,s_1)$ have unit-diameter tetrahedralization. Observe these subtetrahedra form a unit-diameter tetrahedralization of $p_1p_2p_{21}p_{11}s_1$.

Now we examine the elements of the set $S_3$. Without loss of generality we examine the element $p_{21}p_{31}s_{1}s_2$ only. We have $p_{i1}s_j<2$ for $i=2,3$ and $j=1,2$. The proof comes from Lemma 4.

Now we examine the unique element of the set $S_4$. The proof comes from Corollary 1.

Observe these subtetrahedra form a unit-diameter tetrahedralization of $p_1p_2p_{3}q$. This completes the proof of the theorem.