On nontriangulable polyhedra

Abstract

Triangulations of 3-dimensional polyhedron are partitions of the polyhedron with tetrahedra in a face-to-face fashion without introducing new vertices. Schönhardt (Math. Ann. 89:309–312, 1927), Bagemihl (Amer. Math. Mon. 55:411–413, 1948), Kuperberg (Personal communication 2011) and others constructed special polyhedra in such a way that clever one line geometric reasons imply nontriangulability. Rambau (Comb. Comput. Geom. 52:501–516, 2005) proved that twisted prisms over n-gons are nontriangulable. Our approach for proving polyhedra are nontriangulable is to show that partitions with tetrahedra, which we call tilings, do not exist even if the face-to-face-restriction is relaxed. First we construct a polyhedron which is tileable but is not triangulable. Then we revisit Rambau type twisted prisms. In fact we consider a slightly different class of polyhedra, and prove that these new twisted prisms are nontileable, thus are nontriangulable. We also show that one can twist the regular dodecahedron so that it becomes nontileable, which is abstracted to a new family of nontileable polyhedra, called nonconvex twisted pentaprisms.

1 Terminology and an account of known nontriangulable polyhedra

It is well known that every planar polygon can be partitioned into triangles without introducing new vertices. The triangles in these triangulations automatically meet in edge-to-edge fashion, moreover the number of triangles is dependent on the side-number of the original polygon. Surprisingly none of the analogous statements remain true when we move up by one dimension. For more information regarding these properties the texts De Loera et al. (2010), Devadoss and O’Rourke (2011), and O’Rourke (1998) provide a detailed analysis of triangulations. In the rest of this paper we consider polyhedra in 3-space. We start by formally introducing the concepts of triangulations and tilings with tetrahedra of 3-dimensional polyhedra.

Definition 1

A triangulation of a polyhedron P is a collection of tetrahedra that satisfies the following three properties:

Vertex property: The vertices of each tetrahedron are vertices of P.

Union Property: The union of all tetrahedra is P.

Face-to-face Property: Any pair of tetrahedra intersect in a common face (possibly empty).

Definition 2

A tiling with tetrahedra of a polyhedron P (in short tiling of P) is a collection of tetrahedra with disjoint interiors, so that the collection satisfies the Vertex Property and the Union Property of Definition 1. (Sometimes refered to as a dissection in the literature.)

It is a simple exercise to show that the cube has a tiling with tetrahedra which is not a triangulation. Therefore the family of triangulations of a given polyhedron can be a proper subset of the family of its tilings with tetrahedra. It is also obvious that if a polyhedron cannot be tiled with tetrahedra, then it cannot be triangulated. It is somewhat harder to show that the opposite is not true. In Sect. 3, we construct a polyhedron which is nontriangulable but can be tiled with tetrahedra.

The existence of a nontriangulable polyhedra was first shown by Lennes (1911). Lennes constructed a simple connected polyhedron with 7 vertices and 10 triangular faces, where each diagonal contained points on the exterior of the polyhedron. Lennes checked by inspection that every tetrahedron on the vertex set had an edge, which was a diagonal of the polyhedron, thus he desproved the existence of triangulations. (We omit the formal description of Lennes example, since Schönhardt (1927) described a much simpler polyhedron having the same properties.) Schönhardt (Fig. 1) started with a triangular right prism and rotated the top triangle of a triangular prism within its own plane so that each of the quadrilateral faces broke into two triangles along an edge with a nonconvex interior angle. It was easy to see that every diagonal of the new polyhedron lies outside of the twisted prism. Furthermore each of the three tetrahedra on the set of vertices whose base coincides with the bottom triangle has an edge which is a diagonal of the twisted prism, thus ruling out the existence of a triangulation.

Fig. 1

Schönhardt’s twisted triangular prism

Bagemihl (1948) modified Schönhardt’s nonconvex prism to get a new polyhedron with $n \ge 6$ vertices so that every diagonal lies outside of the polyhedron. One of the twisted vertical edges of Schönhardt’s polyhedron was replaced with a suitable concave curve and new vertices were placed along this curve (Fig. 2). Finally, the two rectangles of the prism, which met along the vertical edges, were replaced with a sequence of triangles so that the adjacent triangles meet along an edge with a nonconvex angle. It is easy to see again that any tetrahedron on the vertex set whose base coincides with the bottom triangle has an edge which is a diagonal of Bagamihl’s polyhedron, contradicting the existence of a triangulation.

Fig. 2

Bagemihl’s polyhedron

Fig. 3

Rambau’s twisted prism over a hexagon

Rambau (2005) provided another natural generalization of the Schönhardt’s twisted triangular prism. Rambau considered a right prism over an n-gon and inserted one diagonal on each of the lateral quadrilateral faces so that no two of the inserted diagonals had a common endpoint. Then it was proved that this partial triangulation of the surface cannot be extended to a triangulation of the right prism. In particular, this implied that if the top face of a right prisms is rotated with a sufficiently small angle, in the Schönhardt style, then the twisted prism over the given n-gon cannot be triangulated (Fig. 3).

For completeness, let us point out that there is another famous polyhedron, called Jessen’s orthogonal icosahedron (Fig. 5), all of whose diagonals have points outside of the polyhedron so that any tetrahedron on the vertex set has an edge, which was a diagonal of Jessen’s icosahedron, thus making it nontriangulable. Interestingly, Jessen (1967) constructed the polyhedron named after him for another purpose. He was looking for a polyhedron which had only right dihedral angles without having only axes papallel edges. Figures 4 and 5 explain the construction: start with three 1 by 2 rectangles all at right angles to one another as depicted on Fig. 4. Then get the (nonconvex) Jessen’s orthogonal icosahedron by joining the corners of the rectangles so that it looks like Fig. 5.

Fig. 4

Construction of Jessen’s orthogonal icosahedron

Fig. 5

Front view of Jessen’s orthogonal icosahedron

Ruppert and Seidel (1992) described a simple way for constructing a new nontriangulable polyhedron by gluing a sufficiently small Schönhardt prism along its triangular base to one of the faces of a given polyhedron. If the Schönhardt’s prism was sufficiently skinny, then one easily can assure that diagonals of the new polyhedron cannot pierce the triangular base of the Schönhardt’s prism. Thus, each triangualtion of the new shape, is the union of independent triangulations of the two components. Since Schönhardt’s prism is nontriangulable, the same holds for the combined polyhedron.

The second ingenious idea for constructing nontriangulable polyhedra is to ensure that there is at least one point inside of the polyhedron which does not see any of the vertices. Indeed, if a polyhedron is triangulable then every interior point can see at least four of the vertices of the polyhedron. Kuperberg (2011) removed three pairs of mutually perpendicular tunnels (Fig. 6) and truncated the corners of the initial cube to guarantee that the center of the cube does not ‘see’ any vertex of the new polyhedron. We modified Kuperberg’s polyhedron so that it became simply connected, yet still contained the view obstructing property (Fig. 7). The view obstructing property of the cube with tunnels was used earlier for different purposes. For example, the construction depicted on Fig. 8 was attributed to Thurston by Paterson and Yao (1989). This shape (not the colored blocks, but the region of space surrounding them within the cube) was used to give a bound on the complexity of subdividing the polyhedron into convex regions. The bound followed from the observation that the points in the center of each cubical void cannot see each other, therefore they should belong to different components of the decomposition. The same construction with a slight modification fits our discussion. Let the surrounding body be the convex hull of the colored block minus all the blocks. This body obviously has not only one, but several points which do not see any of the vertices, thus the body is nontriangulable.

Fig. 6

Kuperberg’s polyhedron

Fig. 7

Kuperberg’s example made simple connected

Fig. 8

Thurston’s example

2 Results and outline of the paper

Obviously any nontileable polyhedron is nontriangulable. Theorem 1 in Sect. 3 shows that the converse statement is false. One can easily check that the simple arguments which proved that the polyhedra of Schönhardt’s, Bagamihl’s, Ruppert’s and Sidel’s, Thurston’s, Jessen’s and Kuperberg’s are nontriangulable also prove that they are nontileable. A detailed analysis of Rambau’s paper reveals that from the proof of Rambau it does not follow that his twisted prisms are nontileable. Theorem 2 in Sect. 4 essentially claims that Rambau’s type twisted polyhedra are in fact nontileable. Here the term ‘essentially’ refers to a technical detail in our definition of ’twists’ (see Definition 3). Depending on the shape of the base polygons, ’our twist’ is slightly different from that of Rambau. It will be clear that ’our twists’ are more general for most prisms, but as Theorem 3 in Sect. 4 claims there are some prisms for which Rambau’s twists cannot be achieved with ’our twists’. Since relaxing the face-to-face-restriction leads to the same negative result, the proof of Theorem 2 in Sect. 4 is a new short proof of Rambau’s theorem for those twisted prisms where the two types of twists coincide. Theorem 4 in Sect. 5 claims that one can twist the regular dodecahedron so that it becomes nontileable. In Sect. 6 we describe a new family of polyhedra, called nonconvex twisted pentaprisms, and outline the proof of Theorem 5 which claims that these polyhedra are also nontileable.

3 On a polyhedron which is tileable but is not triangulable

In view of the definitions any nontileable polyhedron is nontriangulable. If a tiling of polyhedron is not a triangulation, then there must be two tetrahedra in the tiling so that they meet along partially overlapping faces. In particular, we have that

Lemma 1

A nontriangulable polyhedron is tileable only if it contains at least four coplanar vertices.

It is easy to see that for sufficiently small twists, Rambau’s nonconvex twisted prisms do not contain 4 coplanar points. Thus Lemma 1 together with Rambau’s theorem imply that Rambau’s twisted polyhedra are nontileable. The following theorem highlights the difference between triangulating and tiling polyhedra.

Theorem 1

There exist polyhedra which are nontriangulable, but can be tiled with tetrahedra.

Proof of Theorem 1

We start by describing our counterexample: let us start with a horizontal unit square $Q= ABCD$ (see Fig. 9 for ordering of the vertices). Choose the point O over this square at unit distance from its center. Next add to this arrangement a segment EF, whose midpoint is O, has length 4, and is parallel to AB (assume E is closer to A, than to B). The convex hull of Q and the segment EF will be referred as upper wedge P. Let wedge $P'$ be the image of P under the reflection over the plane of Q followed by a $90^\circ$ rotation counterclockwise around the vertical line containing O. Label the images of E and F as $E'$ and $F'$ respectively. Finally, we twist the union of these two wedges by rotating the segments EF and $E'F'$ clockwise around their midpoints in their horizontal plane by a small angle $\epsilon$, so that each of the trapezoidal faces of P and $P'$ broke into two triangles along an edge with a nonconvex interior angle (Figs. 10, 11). We will label the twisted images of wedges P and $P'$ by $P_t$ and $P_t'$ and will label the union of them by U.

Fig. 9

Union of two perpendicular wedges

Fig. 10

Transparent view of the twisted wedges

Fig. 11

Front view of the twisted wedges

Next we prove that polyhedron U is nontriangulable: notice that the diagonals $EE', EF', FE'$ and $FF'$ lie outside of the polyhedron U, therefore any triangulation of U is the union of triangulations of $P_t$ and $P_t'$. $P_t$ was constructed so that the diagonals AF and EC lie outside of $P_t$. This implies that neither ABC nor ACD can be faces of tetrahedra contained in $P_t$, so diagonal BD must be an edge of at least one tetrahedron in any triangulation of $P_t$. A similar argument applied for $P_t'$ gives that the diagonal AC is an edge of at least one tetrahedron in any triangulation of $P_t'$. We can thus conclude that U is nontriangulable. However $P_t$ is triangulable by a unique set of tetrahedra, EABD, EBDF and DBCF. By symmetry it is obvious that $P_t'$ is also triangulable, providing that the union of these triangulations is a tiling of U with tetrahedra. $\square$

4 Rambau’s twisted prisms in view of tiling by tetrahedra

Can Rambau’s nonconvex twisted prisms be tiled with tetrahedra? For technical reasons, we start by defining a slightly different class of twisted polyhedra over n-gons (called nonconvex skewed prisms over n-gons) and prove that they cannot be tiled with tetrahedra. Relaxing the face-to-face-restriction leads to the same negative result and yields a second shorter proof of Rambau’s theorem in the case of prisms which are both twisted and skewed.

We will talk about caps over the sides of a given convex n-gon ($n \ge 3$). The region outside of the polygon bounded by a side and the extensions of its two adjacent sides will be called the cap over the selected side (Fig. 12). Note that some caps can be unbounded.

Definition 3

[Nonconvex Skewed Prisms over n-gons ($n \ge 3$)] Let us start with a right prism, whose bottom and top faces (B and U respectively) are horizontal convex n-gons. For visual orientation assume that if we look down at the horizontal planes, then the vertices of B and U and the caps of B are labeled clockwise from 1 to n so that the vertices with the same perpendicular projection have the same label and the label of a cap over the side 12 ($23,34,\ldots , n1$ resp.) is 2 ($3,4,\ldots ,n,1$ resp.) The bottom face B will remain unchanged, while the vertices of the upper face will be moved within their plane so that they lie above the cap with the same index. As we move the vertices of U, each of the vertical quadrilateral faces break into two triangles which meet along an edge with a nonconvex angle (Fig. 13).

Fig. 12

Vertical prism and bottom face B with caps

Fig. 13

Nonconvex skewed prism over a 7-gon

The following two remarks are immediate consequences of the above definition:

Remark 1

Since the diagonal connecting vertex i of B to vertex i of U lies outside of the skewed prism, the vertices i of B and i of U cannot belong to a common tetrahedron in a tiling of the nonconvex skewed prism.

Remark 2

Assume i and j are not consecutive indices modulo n. Let Q be the vertical plane through i and j of U. The construction of U yields that the vertices k of U, $i<k<j$ are exactly those vertices of U, which are not separated by Q from the vertices m of B, $i \le m < j$.

Similarly to Schönhardt’s prisms, both Rambau’s twisted and our skewed prisms were introduced to enhance the family of nontriangulable polyhedra. Rambau proved that sufficiently small rotations of the top face always produce nontriangulable polyhedra. Our main theorem says that in case of skewed prisms we do not have such restriction:

Theorem 2

Nonconvex skewed prisms over a convex n-gon ($n \ge 3$) cannot be tiled with tetrahedra.

It is intuitively expected that in most cases twisted prisms are also skewed. In fact, it takes some effort to construct a counterexample:

Theorem 3

There is a right prism for which no rotation of the top face will produce a skewed prisms.

The rest of this section contains the proof of Theorems 2 and 3. First we will prove Theorem 2. This proof will frequently refer to the following simple, but important lemma:

Lemma 2

Let U and V be two adjacent triangles in plane P sharing an edge e. Assume u and v are points in the same half space bounded by P, so that U and v can be separated from V and u by a plane passing through e. Then the tetrahedra $\mathrm {conv}\{U, u\}$ and $\mathrm {conv}\{V, v\}$ have common interior points.

Proof of Lemma 2

Notice that the two interior dihedral angles along the edge e of these tetrahedra sum to greater than $180^{\circ }$ (Fig. 14) and thus close to the edge e tetrahedra $\mathrm {conv}\{U, u\}$ and $\mathrm {conv}\{V, v\}$ have common interior points. $\square$

Fig. 14

Proof of Lemma

Proof of Theorem 2

If T is a triangulation of a polygon, then $t \in T$ is usually called an ear, if exactly two of its edges are edges of the polygon. We will say that an ear is pruned if it is deleted from the triangulation, making the triangulated polygon smaller. It is a well known fact (Meisters 1975) that every triangulation of an n-gon, where $n > 3$, has at least two ears, thus every triangulation can be pruned.

Consider a nonconvex skewed prism S together with all the notations of Definition 3 (Fig. 13). Indirectly assume that S can be tiled with tetrahedra. Let T be a family of tetrahedra which tile S. The tiling T naturally induces a triangulation of the upper face U. Let $\mathcal {U}$ be the family of those polygons contained by U, called sub-polygons, whose edges are edges of this induced triangulation.

For each sub-polygon $V \in \mathcal {U}$ denote by T(V) the set of those tetrahedra of T, which have a face belonging to the induced triangulation of $\mathcal {U}$. A sub-polygon $V \in \mathcal {U}$ is called non-splitting, if the vertical planes through the sides of V do not intersect the interior of that tetrahedron of T(V) which contains the particular side.

Let $\mathcal {U^*} \subseteq \mathcal {U}$ be the collection of all the non-splitting sub-polygons of U. Remark 1 essentially says that $U \in \mathcal {U^*}$, thus $\mathcal {U^*}$ is not empty. Choose a sub-polygon $P \in \mathcal {U^*}$ with the fewest number of vertices.

We will show that P is a triangle. Assume indirectly that $k > 3$. Since $k > 3$, T restricted to P has at least two ears. Let t be one of these ears. Let $t'$ be the triangle adjacent to t in the induced triangulation of U in P, d be the diagonal along which t and $t'$ meet, and Q be the vertical plane through d. Let $b_u$ and $b_v$ be the vertices of the base polygon B so that $\mathrm {conv}\{t', b_v\}$ and $\mathrm {conv}\{t, b_u\}$ are tetrahedra in T. In view of the assumption that P is non-splitting, Remarks 1 and 2 imply that t and $b_u$ are on different sides of the plane Q. Thus, by Lemma 2, $t'$ and $b_v$ cannot be separated by the same plane Q. Therefore after pruning t, we get a non-splitting polygon $P\!\setminus \!t$ with fewer vertices than P, a contradiction.

Therefore there exists a triangle $t \in \mathcal {U}$ which is a non-splitting sub-polygon, thus along with Remark 2 we see that the only vertices of the bottom base which can be the fourth vertex of the tetrahedron from T which has t as a face have the same labels as the vertices of t. However Remark 1 provides the contradiction since each such tetrahedron will have an edge lieing outside the skewed prism. $\square$

Fig. 15

Proof of Theorem 3

Proof of Theorem 3

Figure 15 depicts a parallelogram, with a pair horizontal sides of unit length and with a unit area. Assume that the other pair of sides have length 100 and also assume that they have a negative slope. This parallelogram is going to be base B of our counterexample. Let us label the vertices of B counterclockwise by 1, 2, 3, 4 so that the upper right vertex has label 1. Notice that the caps $C_i$, $i=1, 2, 3, 4$ associated with base B are half strips (see Fig. 15 for proper labeling). For Theorem 3 we need to show that one cannot rotate B so that each of the caps $C_i$ ($i=1, 2, 3, 4$) contains exactly one vertex of the rotated parallelogram. Notice that the minimum distance between the points of $C_1$ and $C_3$ is realized only for the vertex pair $\{ 1,3 \}$ of parallelogram B. This means that caps $C_1$ and $C_3$ must contain the vertex pair $\{ 2,4 \}$ of the rotated parallelogram. Since B has unit area the distance between the slanted sides is $\frac{1}{100}$. It is easy to see that the slope of the diagonal 13 of the rotated parallelogram is still negative, thus this diagonal is steeper than the diagonal 13 of B. But this contradicts that vertices 1 and 3 of the rotated parallelogram belong to caps $C_2$ and $C_4$.$\square$

5 Nonconvex twisted dodecahedra: a new family of nontileable polyhedra

We would like to show that the proof we used to show that nonconvex skewed prisms cannot be tiled, can be easily extended to verify that other nonconvex twisted polyhedra cannot be tiled. In particular, we will alter the regular dodecahedron to fit our approach.

For visual orientation let us place the regular dodecahedron D with one of its pentagonal faces on a horizontal plane (Fig. 16). We could label the vertices of D from 1 to 20, but that would make the rest of the text very hard to read, therefore we choose another logical, but nonconventional labeling. Let us start by labeling the vertices of the bottom face clockwise—looking down at the horizontal plane—from $1_0$ to $5_0$, where index 0 means that all these vertices belong to the zero level plane. $P_0$ will denote the bottom face of the dodecahedron. Similarly, the vertices of the top face will be labeled clockwise by $1_1$ to $5_1$, where index 1 indicates that all these vertices are at a distance 1 above the zero level plane. $P_1$ will denote the top face of the dodecahedron. Since the remaining 10 vertices belong to two cross sections parallel to the base plane, they naturally will be labeled by $1_a, \ldots , 5_a$, and by $1_b, \ldots , 5_b$, where $a < b$ are the distances of these cross sections from the zero level plane. Figure 16 explains where are the vertices $1_0, 1_a, 1_b$ and $1_1$ relative to each other. We will refer to a triangle with vertices a, b, c by using the terms ‘$\mathrm {conv} \{a,b,c \}$’ or ‘triangle abc ’. Several times we will need to talk about a tetrahedron, determined by one of its triangular faces, say by T, and by its fourth vertex, say by v. We will refer to this tetrahedron by $\mathrm {conv} \{T,v\}$.

Fig. 16

Regular dodecahedron

For a given pair of small numbers $\delta$ and $\epsilon$, we will construct a nonconvex twisted dodecahedron $D(\delta , \epsilon )$. Let us start by rotating the top face $P_{1}$ of D about its center point clockwise by an angle $\delta$ and the bottom pentagon $P_{0}$ about its center counterclockwise by an angle $\epsilon$. Labeling the rotated vertices with their original label will not cause any confusion, since in the rest of the paper we will talk only about the new positions of these vertices. It is natural to call the convex hull of the twelve points $\{ i_0, i_a, i_b, i_1 |i=1, \ldots , 5 \}$ twisted convex dodecahedron. We will focus on what we call nonconvex twisted dodecahedron (Fig. 17), which is the difference body of the twisted convex dodecahedron and the union of ten rather flat convex ‘wedges’. Each of the ten convex wedges is associate with one of the non-horizontal faces of the original dodecahedron. Each wedge is the convex hull of the their vertices of the respected pentagon in their rotated position. These wedges are $conv\{i_{0},(i+1)_{0},(i+1)_{a},(i+1)_{b},(i+2)_{a}\}$ and $conv\{i_{1},(i+1)_{1},(i-1)_{b},i_{b},i_{a}\}$ for $i = 1,2,3,4,5$ so that the indices are taken modulo 5 (Fig. 18).

Fig. 17

Edge diagram of the nonconvex twisted dodecahedron

Fig. 18

Front view of the nonconvex twisted dodecahedron

Remark 3

The diagonals of the form $i_{n}i_{x}$ for $i = 1,2,3,4,5$, $n =0,1$, and $x \in \{a,b\}$ lie outside $D(\delta , \epsilon )$.

Theorem 4

For $0 <\delta < 18^{\circ }$ and $0 <\epsilon < 18^{\circ }$ the nonconvex twisted dodecahedron $D(\delta , \epsilon )$ cannot be tiled by tetrahedra.

Proof of Theorem 4

The outline of the proof is rather straightforward. We will assume indirectly that a tiling of $D(\delta , \epsilon )$ exists. We will study the induced triangulation on $P_1$ and use Lemma 2 to show that at least one triangle of this triangulation belongs to a tetrahedron whose fourth vertex belongs to the bottom pentagon $P_0$. Finally, a case analysis and Lemma 2 will show that this is not possible and thus there is no tiling of $D(\delta , \epsilon )$. The following are the details of this outline:

As in Theorem 2, we will consider a tiling S of $D(\delta , \epsilon )$ and S’s induced triangulation on the upper face of $D(\delta , \epsilon )$. Denote by T this induced triangulation. Since $D(\delta , \epsilon )$ has the same rotational symmetry as its top face we can assume, without loss of generality, that

$$\begin{aligned} T = \left\{ \mathrm {triangle} \ 1_{1}2_{1}3_{1}, \quad \mathrm {triangle} \ 1_{1}3_{1}4_{1}, \quad \mathrm {triangle} \ 1_{1}4_{1}5_{1}\right\} . \end{aligned}$$

For simplicity we will denote triangle $1_{1}2_{1}3_{1}$ by A, triangle $1_{1}3_{1}4_{1}$ by B, and triangle $1_{1}4_{1}5_{1}$ by C (Fig. 19). $\square$

Fig. 19

Top view of $D(\delta , \epsilon )$ with the induced triangulation

Lemma 3

The tiling S contains a tetrahedron such that one of its face is a triangle of the induced triangulation T and its fourth vertex is a vertex of the bottom face $P_{0}$.

Proof of Lemma 3

Recall that there is no tetrahedron in the tiling S with B as a face and containing a vertex from the set $\{1_{a}, 1_{b}, 3_{a}, 3_{b}, 4_{a}, 4_{b}\}$. Similarly there is no tetrahedron in the tiling S with triangle A as a face and containing a vertex from the set $\{1_{a}, 1_{b}, 2_{a}, 2_{b}, 3_{a}, 3_{b}\}$ and there is no tetrahedron in the tiling S with triangle C as a face and containing a vertex $\{1_{a}, 1_{b}, 4_{a}, 4_{b}, 5_{a}, 5_{b}\}$.

Now indirectly assume each tetrahedron containing three points from $P_{1}$ does not contain a fourth point from $P_{0}$. In particular, let us discuss the tetrahedron in the tiling S whose face is the triangle B. If triangle B is the face a tetrahedron which also includes vertex $2_{a}$ or $2_{b}$, then by Lemma 2 triangle A cannot be the face of a tetrahedron containing vertices from the set $\{4_{a},4_{b},5_{a},5_{b}\}$. Thus reaching a contradiction that triangle A is not in a tetrahedron containing a vertex from $P_{0}$.

Similarly, if triangle B is the face of a tetrahedron containing $5_{a}$ or $5_{b}$, then by Lemma 2 triangle C cannot be the face of a tetrahedron containing vertices from the set $\{2_{a},2_{b},3_{a},3_{b}\}$. Thus reaching a contradiction that triangle C is not in a tetrahedron containing a vertex from $P_{0}$. This analysis completes the proof of Lemma 3. $\square$

Returning to the proof of Theorem 4 we assume here exists a tetrahedron of S of the form $\mathrm {conv}\{X,z_{0}\}$ for $X \in \{A,B,C\}$ and $z \in \{1,2,3,4,5\}$ and via a case analysis we will find a contradiction.

Case 1 $s = \mathrm {conv}\{B,z_{0}\}$

• Subcase 1A: $z = 2$ Since the triangular face $3_{1}4_{1}2_{b}$ shares and edge with triangle B we can see by Lemma 2 that the tetrahedron of S having triangle $3_{1},4_{1},2_{b}$ as a face can only have its fourth vertex be from the set $\{3_{a},3_{b},2_{0}\}$, but by construction all tetrahedra of these constraints contain a diagonal lying outside $D(\delta , \epsilon )$, thus a contradiction.

• Subcase 1B: $z = 1,3,4,$ or 5 We will find a contradiction for $z=5$, so $s = \mathrm {conv}\{B,5_{0}\}$. The other three will follow with symmetry and similar arguments.

  Since triangle B and triangle A share edge $1_{1}3_{1}$, then Lemma 2 provides that the tetrahedron of S having triangle A as a face can only have its fourth vertex from the set $\{1_{0},5_{0},1_{a},1_{b},2_{a},2_{b}\}$, but by construction A cannot be the face of a tetrahedron containing the vertices from the set $\{1_{a},1_{b},2_{a},2_{b}\}$.

  Thus, if we assume the tetrahedron $\mathrm {conv}\{A,1_{0}\} \in S$, then by a similar argument as in Subcase 1A the tetrahedra of S having triangle $2_{1}3_{1}1_{b}$ as a face, will have its fourth vertex be from the set $\{2_a,2_b,1_0\}$ but by construction all tetrahedra of these constraints contain a diagonal lying outside $D(\delta , \epsilon )$. Similarly if we assume the tetrahedron $\mathrm {conv}\{A, 5_0\} \in S$, then by a similar argument as in Subcase 1A the tetrahedron of S having triangle $1_{1}2_{1}5_{b}$ as a face, will have its fourth vertex be from the set $\{1_a,1_b,5_0\}$ but by construction all tetrahedra of these constraints contain a diagonal ling outside $D(\delta , \epsilon )$, thus a contradiction.

• Case 2 $s = \mathrm {conv}\{A,z_{0}\}$ (By symmetry a similar argument can be made for triangle C.)

• Subcase 2A: $z= 1$ or 5 We have seen that $z \ne 1$ or 5 by the argument in Case 1-B.

• Subcase 2B: $z = 2$ Since triangular face $2_{1}3_{1}1_{b}$ shares an edge with triangle A, then Lemma 2 along with the construction yields that the tetrahedron of S containing triangle $2_{1}3_{1}1_{b}$ as a face must have as its fourth vertex $2_{0}$. Since triangular face $3_{1}1_{b}2_{a}$ shares an edge with triangular face $2_{1}3_{1}1_{b}$, Lemma 2 provides that the tetrahedron of S containing triangle $3_{1}1_{b}2_{a}$ as a face has as its fourth vertex be from the set $\{1_{0},2_{b},2_{0},3_{a}\}$, but by construction all tetrahedra of these constraints contain a diagonal lying outside $D(\delta , \epsilon )$, thus a contradiction.

• Subcase 2C: $z = 3$ or 4 We will find a contradiction for $z=3$, so $s = \mathrm {conv}\{A,3_{0}\}$. The case of $z=4$ will follow from a similar argument. Recall that Case 1 showed triangle B cannot be in a tetrahedron with a vertex of $P_{0}$. Since triangle A and triangle B share and edge Lemma 2 and the construction provides that the tetrahedron of S containing B as a face has as its fourth vertex $5_{a}$. Since triangle B and triangle C share an edge and B is in a tetrahedron with vertex $5_a$, then by Lemma 2, all tetrahedra not intersecting $\mathrm {conv}\{B,5_a\}$ and containing C as a face has a diagonal lying outside $D(\delta , \epsilon )$, thus a contradiction. $\square$

6 Nonconvex twisted pentaprisms: another new family of nontileable polyhedra

Antiprisms are similar to vertical prisms except the bases are rotated relative to each other and the side faces are triangles, rather than quadrilaterals. In this paper we restrict ourselves to the case of regular antiprisms, where the bases are regular n-sided polygons, and where the top face is rotated around its center by an angle $\frac{180^\circ }{n}$ relative to the bottom face (Fig. 20). Simultaneously rotating all triangular faces of a regular antiprism outward around their horizontal edges by the same angle, the triangular faces became congruent pentagons. Such convex polyhedra will be called regular pentaprisms (Fig. 21). Notice that the regular dodecahedron is a special regular pentaprism. The same twist, which in Sect. 5 changed the regular dodecahedron into nonconvex twisted dodecahedron, will change regular pentaprisms into nonconvex twisted pentaprisms (Fig. 22). In this section we prove that for sufficiently small twists the nonconvex twisted pentaprisms are nontileable.

Fig. 20

Antiprism over hexagonal base

Fig. 21

Pentaprism over hexagonal base

Fig. 22

Twisted pentaprism over hexagonal base

Theorem 5

Let P be a regular pentaprism over a regular n-sided base. Twisting the top and bottom faces of P in opposite direction by an angle $\le \!\!\!\frac{360}{4n}^{\circ }$ will result in a nonconvex twisted pentaprism which cannot be tiled by tetrahedra.

Proof of Theorem 5

Indirectly assume that a nonconvex twisted pentaprism can be tiled by tetrahedra. Again we will study the triangulation of the top face induced by one of these tilings. It is easy to show that Lemma 3 holds for the induced triangulation of the top face and thus the tiling of the nonconvex twisted pentaprism has a tetrahedron containing three vertices from the top face and one vertex from the bottom face. Finally, we use a case analysis hinging on a generality of Lemma 2 to contradict the existence of tiling of the nonconvex twisted pentaprism. The details of such case analysis are similar to those used in the proof of Theorem 4 and thus are omitted here.$\square$