Triangulations and Simplex Tilings of Polyhedra by Braxton Carrigan A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 4, 2012 Keywords: triangulation, tiling, tetrahedralization Copyright 2012 by Braxton Carrigan Approved by Andras Bezdek, Chair, Professor of Mathematics Krystyna Kuperberg, Professor of Mathematics Wlodzimierz Kuperberg, Professor of Mathematics Chris Rodger, Don Logan Endowed Chair of Mathematics Abstract This dissertation summarizes my research in the area of Discrete Geometry. The par- ticular problems of Discrete Geometry discussed in this dissertation are concerned with partitioning three dimensional polyhedra into tetrahedra. The most widely used partition of a polyhedra is triangulation, where a polyhedron is broken into a set of convex polyhedra all with four vertices, called tetrahedra, joined together in a face-to-face manner. If one does not require that the tetrahedra to meet along common faces, then we say that the partition is a tiling. Many of the algorithmic implementations in the eld of Computational Geometry are dependent on the results of triangulation. For example computing the volume of a polyhedron is done by adding volumes of tetrahedra of a triangulation. In Chapter 2 we will provide a brief history of triangulation and present a number of known non-triangulable polyhedra. In this dissertation we will particularly address non-triangulable polyhedra. Our research was motivated by a recent paper of J. Rambau [20], who showed that a nonconvex twisted prisms cannot be triangulated. As in algebra when proving a number is not divisible by 2012 one may show it is not divisible by 2, we will revisit Rambau?s results and show a new shorter proof that the twisted prism is non-triangulable by proving it is non-tilable. In doing so, we identify a new family of nonconvex non-tilable polyhedra, which we call an altered right prism. Furthermore we will perturb the vertices of a regular dodec- ahedron in a twisted manner resulting in a non-tilable polyhedra. Also for completeness, we describe two concrete non-triangulable polyhedra which can be tiled with tetrahedra. From observations made about the provided non-triangulable polyhedra, we started to systematically study extensions of surface triangulations of convex polyhedra. Among others we proved that if each vertex of a convex polyhedron is adjacent to no more than ii three non-triangular faces, then for every surface triangulation one can perturb the vertices of the polyhedron so that the resulting polyhedron is combinatorially equivalent to the given surface triangulation. iii Acknowledgments I would like to thank all of my committee members for their suggestions and support in completing this text. Mostly I am indebted to Dr. Andras Bezdek for the hours he spent discussing the contents of this dissertation. His guidance through this process will forever leave a mark on my career. I could not have completed my degree without his assistance. I am also indebted to my entire family for their continued loving support. Speci cally I wish to thank my wife Catie for her love, support, and patience while I pursued my Ph.D. I am truly blessed to have a multitude of friends, family, and colleagues who have continually given me strength to pursue my goals. iv Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Illustrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Brief History of Triangulation and Terminology . . . . . . . . . . . . . . . . . . 4 2.1 History of Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Complexity and NP-Complete . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Non-Triangulable Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Tiling by Simplices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Non-Triangulable Polyhedra which can be Tiled by Tetrahedra . . . . . . . . 23 3.3 Non-Tilable Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.4 Open Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4 Extendable Surface Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4.1 Realizing Surface Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Polyhedra with Regular Polygonal Faces . . . . . . . . . . . . . . . . . . . . 46 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 A Johnson Solids Containing Fan Vertices in every Surface Triangulation . . . . . 58 v List of Illustrations 2.1 A triangulation determined by a lower envelope of a lift . . . . . . . . . . . . . 6 2.2 Delauney triangulation and Voronoi diagram . . . . . . . . . . . . . . . . . . . . 6 2.3 A partition into triangles which is not a triangulation . . . . . . . . . . . . . . . 7 2.4 Flips in two and three dimensional space . . . . . . . . . . . . . . . . . . . . . . 8 2.5 Graph of triangulations of a hexagon . . . . . . . . . . . . . . . . . . . . . . . . 8 2.6 Triangulations of di erent cardinality . . . . . . . . . . . . . . . . . . . . . . . . 9 2.7 Sch onhardt?s twisted triangular prism . . . . . . . . . . . . . . . . . . . . . . . 12 2.8 Bagemihl?s polyhedron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.9 Attaching Sch onhardt?s twisted prism to a cube . . . . . . . . . . . . . . . . . . 14 2.10 Jessen?s orthogonal icosahedron . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.11 Thurston?s polyhedron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.12 Chazelle?s polyhedron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.13 Nonconvex twisted prism SC6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.14 Right prism PC6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Tiling a cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 vi 3.2 A non-triangulable polyhedron which can be tiled with tetrahedra . . . . . . . . 23 3.3 A non-triangulable polyhedron which can be tiled with tetrahedra . . . . . . . . 25 3.4 Labeling the translated cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.5 Intersecting tetrahedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.6 All regions Ri for C7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.7 Polyhedron BC7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.8 Halfplanes c+ and c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.9 Polygonal base with no rotational center . . . . . . . . . . . . . . . . . . . . . . 32 3.10 Edge graph of DH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.11 Edge graph of DH( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.12 Top view of DH( ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.1 Tiling of a cube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.2 Extended tiling which crosses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.3 Transforming a degenerate polygon into a semi-concave polygon . . . . . . . . . 44 4.4 Vertex labeling of the cuboctahedron . . . . . . . . . . . . . . . . . . . . . . . . 49 4.5 Slicing the rhombicuboctahedron . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.6 Edge graph of a partial surface triangulation of the truncated tetrahedron . . . 52 4.7 Edge graph of a partial surface triangulation of the truncated cube . . . . . . . 53 vii Chapter 1 Introduction Geometry is a subject as old as mathematics itself. Most of the early theorems and proofs of mathematics were a result of studying point and line con gurations. With the development of abstract geometries such as topology and di erential geometries, much of the classical concrete problems of geometry seemed to be neglected. While some of the great mathematicians such as Cauchy, Gauss, and Kepler dabbled in such topics, it appeared that the geometries of the Greeks and Euclid were only used for teaching purposes. With the insurgence of technology and the necessity for algorithmic solutions, came a rebirth of research interest into the more concrete geometric structures and so the intuitive geometric questions posed by Thue and Minkowski gave birth to the subject of Discrete Geometry. Later L. Fejes T oth [10] and [11] formalized this eld of mathematics which he initially called \Intuitive Geometry". Currently W. Kuperberg and others are translating Fejes T oth?s German monograph [11] into English. Many other monographs and survey papers have since been written in an attempt to compile the up to date results of the eld. Some of the larger compilations are by P. Argawal and J. Pach [18], C. Rogers [21], and P, Brass, W. Moser and J. Pach [4]. By the mid 20th century many mathematicians were looking for answers to the simply stated geometric questions of optimization and packing problems and it would not be long until we would nd useful application for the results of these early discrete geometers. In the 1970?s the growing areas of Computer Science such as Computer Graphics, Robotics, Algorithmic Design, Geographic Information Systems, Coding Theory and others spawned the area of Computational Geometry. Some recent introductory texts which have compiled 1 some of the newest results in this eld are [8] and [3]. It is worth noting one of the earliest monographs in this eld was compiled by H. Edelsbrunner [9]. Today Discrete Geometry and Computational Geometry are often combined as the two areas study similar problems, in fact they frequently use results from one another. This dis- sertation contains four results, each associated with the area of Discrete and Computational Geometry, which constitutes my research during the period of 2010-2012. We will provide formal de nitions and theorems throughout the text, but the purpose of this introduction is to present the motivation for choosing this topic and informally present our results. The speci c problems we will discuss concern three dimensional polyhedra and their partitions into tetrahedra. A partition is called a triangulation if the tetrahedra are joined together in a face-to-face manner. If one does not require that the tetrahedra meet along common faces, then we say that the partition is a tiling. We will also consider extensions of surface triangulations to triangulations (tilings resp.). My research started by reading a recent paper of Rambau [20], who showed that twisted prisms cannot be triangulated. It did not take long to realize that triangulation is an ex- tensively studied area with large amounts of literature and many applications. For example computing the volume of a polyhedron is done by adding volumes of tetrahedra of a trian- gulation. Three dimensional problems usually are more di cult than their planar counterparts, and in the area of triangulation there are surprisingly many di erences between the planar and the three dimensional versions. For example everybody knows that every polygon can be triangulated, moreover the number of triangles is the same in each triangulation. Neither of these hold for triangulations of polyhedra, and thus the characterization of non-triangulable polyhedra is a very di cult open problem. We aim to describe new families of non-triangulable polyhedra. Before presenting our original results, we will provide a brief overview of the history of triangulation and discuss seven known examples of non-triangulable polyhedra. In particular Rambau [20] showed that 2 no triangulation of a prism uses the set of cyclic diagonals along the lateral faces to prove that the twisted prism cannot be triangulated. After reading the details of Rambau?s paper, it is natural to ask if there exist a tiling of a twisted prism. This question motivated the research which is summarized in this dissertation. The dissertation contains the following new results. Examples 8 and 9 are non-triangulable polyhedra which can be tiled by tetrahedra. Theorem 3.4 gives an in nite family of non-tilable polyhedra. The family of tilings not only includes the family of triangulations, but also allows a di erent approach when proving non-existence. In fact we revisited Rambau?s corollary on twisted prisms and present a new and shorter proof. We will further generalize our technique to present another family of non-tilable poly- hedra in Theorem 3.8, further demonstrating the non triviality of tiling by tetrahedra. From the observations of the techniques presented in showing a polyhedron is non- triangulable, we will show how negative results of extendable surface triangulations can produce non-triangulable polyhedra. We will provide both positive and negative results of extendable surface triangulations on Archimedean and Johnson Solids. 3 Chapter 2 Brief History of Triangulation and Terminology Triangulation is of great concern and has many applications, in fact Devadoss and O?Rourke [8] state that \ triangulations are the prime factorizations of polygons, alas with- out the bene t of the \Fundamental Theorem of Arithmetic" guaranteeing unique factor- ization." This statement alludes to the di culties of dealing with the non-unique nature of triangulation and its importance to the eld of geometry. Triangulation has become such a useful partitioning that entire chapters of texts are devoted to the topic and there is even a monograph by J. De Loera, J. Rambau, and F. Santos [7] providing a detailed history of the algorithms and applications surrounding triangulation. De nition 1. A triangulation of a point con guration A in the Euclidean n space, denoted as Rn, is a collection of d-simplices, all of whose vertices are points in A and satis es the following two properties: 1. The union of all the simplices equals conv(A). (Union Property) 2. Any pair of the simplices intersect in a common face (possibly empty). (Intersection Property) Throughout the text we will partition n-dimensional polytopes, where the 2 dimensional polytope is called a polygon and the 3 dimensional polytope is called a polyhedron. A polygon is a closed region whose boundary is a polygonal chain with no self intersections. We call the boundary segments edges, and the points where the edges meet will be called vertices. Unless otherwise stated we will require that two adjacent line segments are not collinear. A polyhedron is the three dimensional analogue of a polygon which is an enclosed region of R3 bounded by nitely many polygons so that if two polygons intersect, they do so along 4 a common edge or vertex. In a polyhedron no two adjacent faces are coplanar. Therefore a polytope is the n-dimensional analogue of a polygon which is an enclosed region of Rn bounded by nitely many n 1 dimensional polytopes joined edge to edge, where an edge is the n 2 dimensional boundary of the n 1 dimensional polytope boundaries, so that if two n 1 dimensional boundary polytopes intersect, they do so along a common boundary. 2.1 History of Triangulation There exist many algorithms which attempt to triangulate a point set and each algorithm must rst depend on nding the convex hull, which has been shown to have complexity O(nlogn). (We will brie y discuss complexity in a later section of this chapter.) Surprisingly the complexity of triangulating a point set has the same complexity as nding its convex hull. In this introduction we will present techniques used for triangulation, yet we will not give the details of such algorithms or complexity arguments. Many triangulation algorithms use a step called lifting (Figure 2.1) and as an extension bending. A lift of a point con guration A is constructed by assigning a height !i > 0 to every ai2A, thus giving a point con guration ^A2Rm+1. The lower envelope of a lift is the face structure of the convex hull of ^A seen from below (the Rm plane). A triangulation of a point con guration A 2 Rm is regular if it is a projection of a lower envelope of a lifting of A. Bending is similar to lifting yet involves assigning heights to a subset of the points while leaving the complement at height 0. Di erent envelopes are considered depending on the application of the bend. 5 Figure 2.1: A triangulation determined by a lower envelope of a lift One should notice that points in the interior of the convex hull are not necessarily vertices of a simplex of the triangulation. A triangulation is full if every point of the point set is a vertex of at least one simplex in the triangulation. One of the most frequently used regular triangulation is the Delauney Triangulation which can be found by lifting the point set onto the Rm+1 paraboloid, then projecting the lower envelope of the lift back onto the Rm space. Interestingly the Delauney Triangulation is the dual of the Voronoi Diagram. De nition 2. For every point p of a point set S, we de ne the Voronoi Region to be all points x2Rm such that jx pj jx qj for all q2S. The Voronoi Diagram is the collection of all points in Rm which have more than one nearest neighbor, or the boundaries of the Voronoi Regions. Figure 2.2: Delauney triangulation and Voronoi diagram 6 Our new results will concern triangulations of polyhedra in R3. A triangulation of a polyhedron P is a partition into nitely many non-overlapping tetrahedra joined face-to- face. In our original results we restrict ourselves to triangulations where the vertices of each tetrahedron are a subset of the vertex set of P. Since we will be concerned with triangulations of polyhedra, all triangulations will be full. Two-Dimensional Triangulations Let us rst investigate the intersection property of triangulation of a point set in R2. In Figure 2.3 we notice the shaded region is a triangle, but the neighboring triangles do not share the entire edge, and thus the con guration is not a triangulation. We may wish to refer to the shaded region as a quadrilateral to emphasize it has four vertices of existing triangles in the partitioning along its boundaries. This is a situation when we wish not to have the angle between two adjacent edges of a polygon be 180o. Figure 2.3: A partition into triangles which is not a triangulation To avoid ambiguity with such con gurations, it is common to consider the point set to be in general position which in this context means that no three points are collinear. Since our results are concerned with triangulating polyhedra it will not be possible to have a vertex lying on the edge of a triangle, so this issue will not arise. 7 There exist many interesting combinatorial results concerning triangulations in R2, of which many hinge on the concept of ips. Two triangulations are ips of one another if the same partitioning is obtained by deleting a diagonal of a convex quadrilateral (or interior vertex of a triangle with its incident edges) from each of the triangulations. (In R3 almost triangulations are obtained from deleting common faces, edges, or a vertex.) Flipsin2dimensionalspace: Flipsin3dimensionalspace: Figure 2.4: Flips in two and three dimensional space In two dimensional space it is common to use a graph of triangulations (Figure 2.5) where each node is a triangulation and the edges between nodes represent a ip. C. Lawson [14] showed that the ip graph is connected. Therefore implying that any two triangulations can be transformed to one another through a series of ips, which has not been shown for higher dimensions. Figure 2.5: Graph of triangulations of a hexagon 8 The connectedness of the ip graph can be helpful in nding combinatorial results in R2 on both point con gurations and polygons. Two important combinatorial results are: Theorem 2.1. Let T be triangulation of a point con guration A 2 R2, where n is the number of points in A and c is the number of points in A lying on the boundary of conv(A), then T contains 2n c 2 triangles. Theorem 2.2. The number of triangulations of a convex n-gon is the (n 2)th Catalan number, where the nth Catalan number is de ned as Cn = 1n+1 2nn . Triangulation in Higher Dimension While the graphs of triangulations have been highly useful in R2, the process of combi- natorially classifying triangulations becomes di cult in R3. The most elementary counting problems, such as how many tetrahedra are included in a triangulation, are daunting in higher dimensional spaces. As seen in Figure 2.6, not every triangulation of a polyhedron consist of the same number of tetrahedra. Figure 2.6: Triangulations of di erent cardinality The non-uniqueness provides di culties for combinatorial results in higher dimensional spaces, yet there do exist some results concerning the number and the existence of triangu- lations. Four such results are listed below along with an important conjecture. Goodman and Pach [12] utilized the concept of bending to show: 9 Theorem 2.3. If A and B are disjoint convex polytopes in Rn, then the closure of ConvfA[ Bg A B can be triangulated. and Theorem 2.4. If A and B are convex polytopes in Rn, with B A, then the closure of A B can be triangulated. The same year Sleator, Tarjan, and Thurston [23] also provided some combinatorial results for triangulations in R3. Theorem 2.5. Let A be a point con guration in R3, then there exists a triangulation of A with no more than 2v 7 tetrahedra, where v is the number of vertices in conv(A). and Corollary 2.6. Every polyhedra of R3, with n 13 vertices, has a triangulation (with the introduction of new vertices, called Steiner points) with at most 2n 10 tetrahedra. The proof of Theorem 2.5 uses a fan argument which we will discuss later in the text when nding extendable surface triangulations. From these results Sleator, Tarjan, and Thurston [23] conjecture: Conjecture 2.7. For every three-dimensional polyhedron with n 13 vertices, there exist no triangulation with less than 2n 10 tetrahedra and its ip graph contains a hamiltonian cycle, which contain every vertex of the ip graph. 2.2 Complexity and NP-Complete Questions which can be answered with a simple yes or no, such as \can a particular polyhedron be triangulated?" are called decision problems. Decision problems can be an- swered by an algorithm which through a series of questions, or steps, arrives at the yes or no answer. Algorithms are measured for e ectiveness by their time complexity, or how long 10 it will take the algorithm to answer the question. Time is measured by the number of steps an algorithm takes to arrive at an answer. Given a variable n of the decision problem, if the algorithm solves the question in fewer than a constant multiple of a function f(n) steps, then we say the algorithm?s complexity is O(f(n)). Speci cally we say an algorithm is in polynomial time, if its complexity is O(nk) for some whole number k. One can study algorithms that run either on deterministic or nondeterministic comput- ers. A deterministic computer is the typical computer which goes through a series of yes and no questions until it determines a nal solution. A non-deterministic computer is allowed unlimited parallel computing meaning it has the ability to explore the options of yes and no simultaneously and do so at every step. A decision problem is in the complexity class P if there exists an algorithm operating on a deterministic computer which can arrive at the answer in polynomial time. A decision problem is in the complexity class NP if there exists an algorithm operating on a non- deterministic computer which can arrive at the answer in polynomial time and a deterministic computer can check the answer in polynomial time. So it is obvious that P NP. Within the class of NP problems we call a decision problem NP-complete if we can show it is NP and all NP problem can be reduced to it in polynomial time. Therefore if we can reduce a decision problem in polynomial time to a known NP-complete problem, then it is NP-complete. The rst NP-complete problem that all others can be reduced to in polynomial time was given by Steve Cook in 1971. If someone can nd an algorithm operating on a deterministic machine which solves any NP-complete problem in polynomial time, then this algorithm would solve all NP problems on a deterministic machine in polynomial time concluding that P = NP, one of the well known unsolved problems in mathematics today. Although signi cant progress has been made in triangulations of higher dimensions, the most compelling result appeared in 1992 by Ruppert and Seidel [22]. 11 Theorem 2.8. It is NP-Complete to decide whether a given three-dimensional polyhedron can be triangulated without using additional Steiner points. 2.3 Non-Triangulable Polyhedra The results of this dissertation are motivated by one of the unsolved problem in [8]. O?Rourke and Devadoss ask to, \Find characteristics that determine whether or not a poly- hedron is tetrahedralizable. Even identifying a large natural class of tetrahedralizable poly- hedra would be interesting." (O?Rourke and Devadoss use the synonymous term tetrahedral- izable for triangulable.) It was rst shown in 1911 by Lennes [15] that not all three-dimensional polyhedra are triangulable. We will provide seven other known examples of non-triangulable polyhedra in this section. Example 1 (Sch onhardt [24]) Figure 2.7: Sch onhardt?s twisted triangular prism One of the most frequently quoted and simplest examples was given by Sch onhardt [24] in 1927. Sch onhardt made a nonconvex twisted triangular prism (Figure 2.7) by rotating the top face of a right triangular prism so that a set of cyclic diagonals became edges with interior dihedral angles greater than 180o. Claim: Sch onhardt?s twisted triangular prism cannot be triangulated. 12 Proof: Every diagonal of the polyhedron lies outside the polyhedron. Therefore any tetrahedron containing four vertices of the twisted triangular prism will contain at least one edge lying outside the polyhedron. Example 2 (Bagemihl [1]) Figure 2.8: Bagemihl?s polyhedron In 1948, Bagemihl [1] modi ed Sch onhardt?s idea to construct a nonconvex polyhedron with n 6 vertices. Figure 2.8 is constructed by replacing one of the twisted vertical edges from Sch onhardt?s twisted triangular prism with a concave curve and placed n 6 vertices along the curve so that the interior dihedral angles of an edge between these new vertices and the vertices of the twisted triangular prism is greater than 180o. Claim: Bagemihl?s generalization cannot be triangulated. Proof: If a triangulation exists, then the top triangular face must be a face of some tetrahedron of the triangulation. For every vertex v, not on the top face, there is a diagonal from v to some vertex on the top face which lies outside the polyhedron. Therefore there is no tetrahedron from the vertex set with the top face as a boundary lying inside the polyhedron. Example 3 (Ruppert and Seidel[22]) 13 Figure 2.9: Attaching Sch onhardt?s twisted prism to a cube Another idea of creating non-triangulable polyhedron with large number of vertices was presented by Ruppert and Seidel [22]. They attached a copy of a non-triangulable polyhe- dron to another polyhedron. Figure 2.9 shows a polyhedron where a copy of Sch onhardt?s nonconvex twisted triangular prism, called a niche, is attached to a face of a cube. Although the union of a cube and Sch onhardt?s nonconvex twisted triangular prism (Figure 2.9) is not a polyhedron by our de nition, this is sometimes considered a polyhedron by those wishing to de ne a polyhedron to be homeomorphic to a ball. To satisfy our de nition we could attach a niche to other polyhedron along a common face so that the desired properties still hold. Claim: If the base of the niche is small enough then Ruppert?s and Seidel?s polyhedron cannot be triangulated. Proof: It can be arranged that those vertices of the Sch ohardt prism which do not lie on the face of the cube do not see any vertex of the cube. Since each diagonal to the non-attached base of the triangular prism lies outside the polyhedron, then there must exist a tetrahedron contained inside the non-convex twisted triangular prism. We know from Example 1 this is not possible, so no set of tetrahedra triangulates the union. Example 4 (Jessen [13]) 14 Figure 2.10: Jessen?s orthogonal icosahedron The orthogonal icosahedron (Figure 2.10) was discovered in 1967 by Jessen [13] while looking for an answer to a rigidity problem. To construct the Jessen polyhedron (Figure 2.10), rst take three pairwise orthogonal rectangles all sharing a common center with side length in a ratio of 1 : p2, so that no two edges from di erent rectangles intersect. Now take the convex hull of the set of 12 vertices of the three rectangles, forming an irregular icosahedron, and remove the six tetrahedra which have two adjacent triangles along an edge of length 1. Claim: Jessen?s polyhedron cannot be triangulated. Proof: As shown in the claim of Bagemihl?s generalization, a polyhedron P cannot be triangulated if there exists a face F such that for every vertex v 2 P, v =2 F, there is a vertex w2F where the diagonal vw is not contained completely inside P. Any triangular face created by the removal of a tetrahedron is such that any vertex not on this face has a diagonal between this vertex and one of the vertices of the face protruding outside the polyhedron. Example 5 (Thurston et al. [19]) Thurston?s polyhedron (Figure 2.11), attributed to Thurston by Paterson and Yao [19], is made from removing 18 non-intersecting square prisms, six from each pair of parallel faces, from the cube. Although this is not considered a polyhedron by our de nition, we still nd the construction relevant to triangulations of polyhedra and we can slightly modify this shape 15 Figure 2.11: Thurston?s polyhedron to become a polyhedron. It is important to note that this polyhedron was independently discovered by several people including W. Kuperberg, Holden, and Seidel. Claim: Thurston?s polyhedron cannot be triangulated. Proof: We say that a point in a polyhedron \sees" another point in the polyhedron if the line segment between the two points is contained inside the polyhedron. We observe that each point of a tetrahedron can see each of the tetrahedron?s vertices. If a polyhedron contains a point which does not see at least four non-coplanar vertices of the polyhedron, then it cannot be contained in a tetrahedron from a triangulation. In Thurston?s polyhedron, the center of the cube does not see any vertex of the polyhedron, thus obviously not in the interior of a tetrahedron of a triangulation. Example 6 (Chazelle [5]) Figure 2.12: Chazelle?s polyhedron 16 In an attempt to create triangulation algorithms, computational geometers have intro- duced the use of Steiner points, or new vertices on existing edges, to allow each polyhedron to be triangulated. Although our aim is to triangulate polyhedra without introducing new vertices, the results of such a process can be useful. Chazelle started with a rectangular prism oriented with one edge along the z-axis con- taining the origin. Let wedges on the bottom face be parallel to the x-axis, and wedges on the top face be parallel to the y-axis. Each wedge?s edge is within epsilon of the hyperbolic parapaloid z = xy so that no two wedges intersect. The polyhedra obtained from deleting all the wedges from the rectangular prism is the Chazelle Polyhedron (Figure 2.12). Claim: Chazelle?s polyhedron cannot be triangulated. Proof: A surprising connection was found by Eppstein between our problem and the problem of nding a lower bound on the number of convex pieces into which any polyhedron of n vertices can be partitioned. Chazelle [5] constructed a polyhedron which can not be partitioned into fewer then O(n2) convex polyhedra. Coincidently his polyhedron spans at most O(n) tetrahedra, which excludes the existence of a triangulation. Example 7 (Rambau [20]) Rambau [20] discovered another generalization of the Sch onhardt twisted triangular prism, which he calls the nonconvex twisted prism (Sch onhardt prism). LetCn be a convex polygon with n vertices, where the vertices ofCn are labeled clockwise as v1;v2;:::;vn. The right prism over Cn (Figure 2.14) is PCn = convf(Cn f0g) [ (Cn f1g)g. To construct the nonconvex twisted prism, pick a point O in the interior of Cn and rotate Cn clockwise about O by . Label the vertices of Cn( ), v1( );v2( );:::;vn( ), corresponding to the vertices of Cn. The convex twisted prism over Cn is PCn( ) = convf(Cn f0g)[ (Cn( ) f1g)g. 17 Figure 2.13: Nonconvex twisted prism SC6 (v4,0) (v1,0) (v2,0)(v3,0) (v5,0)(v6,0) (v1,1) (v2,1)(v3,1) (v4,1) (v5,1) (v6,1) Figure 2.14: Right prism PC6 The non-convex twisted prism over Cn (Figure 2.13) is: SCn = PCn( ) - convf(vi,0),(vi+1,0),(vi( ),1),(vi+1( ),1)g, for all i2(1;n) taken modulo n. Rambau [20] proves: Theorem 2.9. No right prism PCn, for n 3, admits a triangulation that uses the cyclic diagonals f(vi,0),(vi+1,1)g. Which implies Corollary 2.10. For all n 3 and all su ciently small > 0, the non-convex twisted prism SCn cannot be triangulated. Since our new results are closely related to Rambau?s results we wish to discuss the techniques used in his proof. 18 Theorem 2.9 Proof Overview Assume PCn is triangulated so that each cyclic diagonal is an edge of at least one tetrahedron. Rambau observes that every tetrahedron in the triangulation of PCn contains at least one vertex on each base of the prism. Therefore Rambau is able to view each tetrahedron of the triangulation in a cross section of PCn. So he chooses a hyperplane parallel to the base which intersects the prism near (Cn f1g). Rambau also observes that the intersection of the hyperplane and the prism, a copy of Cn which he calls Sn, is subdivided into regions called mixed cells. The mixed cells are the intersections of the hyperplane and the tetrahedra from the triangulation. There are three types of mixed cells in the subdivision of Sn. A tetrahedron containing three vertices from the bottom and one vertex from the top intersects the hyperplane in a small triangle, called a short mixed triangle, and a tetrahedron containing three vertices from the top and one vertex from the bottom intersects the hyperplane in a large triangle, called a long mixed triangle. He labels the boundaries of each short triangle as short edges and large triangles as long edges. Any tetrahedron which has two vertices on the top and two vertices from the bottom will intersect the hyperplane in a parallelogram, called a mixed parallelogram, with two parallel short edges and two parallel long edges. Furthermore, each boundary of a mixed cell is parallel to an edge or diagonal of Sn. Also the intersection property of triangulation provides that mixed cells intersect each other along an entire edge. Each parallelogram is adjacent to at least one short triangle and one long triangle. Also Rambau notices that the edges of Sn are partitioned into one short edge and one long edge which correspond to the diagonal on a lateral face used by the triangulation. Therefore since we are assuming the cyclic diagonals are edges of tetrahedra, we know the mixed edges alternate along the perimeter of Sn to correspond with the cyclic diagonals. For every edge of Sn there is a vertex of the mixed subdivision on the edge separating the long mixed edge and short edge. So we assume the mixed subdivision of Sn contains these edges. He starts along the short mixed edge on a boundary edge, and knowing the two 19 neighboring edges along the boundary are long edges the mixed cell containing this edge has a vertex in the interior of Sn. Now he orders the halfplanes, bounded by diagonals in the projection of (Cn f0g) onto Sn at each short edge on the perimeter of Sn, as positive if it contains the short edge and negative otherwise. Then he looks at the cells on the positive side of of each diagonal and shows that no mixed parallelogram is on the positive side of both its short edges. Finally by the connectedness of the subdivision through adjacent mixed cells, he nds a contradiction that at least one mixed parallelogram is on the positive side of both its short edges. Therefore no triangulation of PCn uses the set of cyclic diagonals. 20 Chapter 3 Tiling by Simplices 3.1 Terminology For our new results, we will introduce new concepts which have been alluded to by previous results, yet we wish to formally de ne such concepts in this dissertation. First we will introduce the concept of tiling by simplices, which weakens the intersection property of triangulation. De nition 3. A tiling by simplices of a point con guration A 2 Rd is a collection of d-simplices, all of whose vertices are points in A, which satis es the following two properties: 1. The union of all the simplices equals conv(A). (Union Property) 2. The intersection of any two simplices (possibly empty) is a subset of a Rd 1 space. (In- tersection Property) Speci cally in R3, a tiling by tetrahedra of a polyhedron P is a partition into nitely many tetrahedra such that the intersection of two tetrahedra (possibly empty) is a subset of a plane. Remark 1. Figure 3.1 describes a tiling of the cube which is not a triangulation. De nition 4. A surface triangulation of a polyhedron P is the triangulation of the faces of P. We will denote the set of diagonals as P and the set of triangles bounded by P and the edges of P as ^P. De nition 5. We say a surface triangulation of a polyhedron P is extendable if there exist a triangulation of P where every t2 ^P is a face of a tetrahedron of the triangulation. 21 Dissectthecubedownthediagonalplane. Triangulateeachpiecesothatits dotteddiagonalisused. Figure 3.1: Tiling a cube De nition 6. A (Sch onhardt type) realization ~P, of a surface triangulation of a convex polyhedron P, is a polyhedron which is constructed from moving vertices of P within an - neighborhood such that every d2 P is an edge of ~P with a concave interior dihedral angle and every edge of P is an edge of ~P with a convex interior dihedral angle. Thus every t2 ^P becomes a face of ~P. Remark 2. The Sch onhardt twisted triangular trism (Figure 2.7 on page 12) is a Sch onhardt type realization of a surface triangulation on the right triangular prism. Remark 3. In Chapter 4, we will classify a set of polyhedra where every surface triangulation can be realized. As previously stated, we wish to re-prove Corollary 2.10, yet we will make an even stronger claim that SCn cannot be tiled by tetrahedra. Figure 3.1 clearly shows that a tiling 22 by tetrahedra exists for PC4, which is not a triangulation. Furthermore, this shows that there exists such a tiling which uses the cyclic diagonals of the cube. We will present a new approach for showing a polyhedron is non-triangulable by showing it is unable to be tiled by tetrahedra. We will also demonstrate how this technique can be used for other polyhedra. Since Rambau?s technique only applies if a hyperplane intersects every tetrahedron from the triangulation, we will provide a family of non-tilable polyhedra in Theorem 3.8 where a hyperplane would not intersect every tetrahedra of a triangulation. Let us rst provide two examples of non-triangulable polyhedra which can be tiled by tetrahedra. 3.2 Non-Triangulable Polyhedra which can be Tiled by Tetrahedra Theorem 3.1. There exist a polyhedron which is not triangulable, but can be tiled by tetra- hedra. Proof We will present Examples 8 and 9 as such polyhedra. Example 8 E F A B CD Eprime Fprime O Figure 3.2: A non-triangulable polyhedron which can be tiled with tetrahedra Start with a horizontal unit square Q. Let A;B;C and D be the vertices of Q in counterclockwise order when we look down at the square from above. Let the point O be over Q at unit distance from its vertices. 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 23 B). Rotate this segment clockwise (i.e. opposite to the order of the vertices A;B;C and D) around the vertical line through O by a small angle . Let P be a non-convex polyhedron bounded Q and by six triangles EAB, EBF, BFC, CDF, EFC, and EDA. Finally let P0 be the image of P under the re ection around the plane of Q followed by a 90 rotation around the vertical line containing O. Label the images of E and F as E0 and F0 respectively. First notice that P is triangulable as it is the union of the tetrahedra EABD;EBDF and DBCF. Since the same holds for P0 we have that the union of P and P0 can be tiled by tetrahedra. Next we show that the union of P and P0 is not triangulable. Since neither E nor F can see the vertices E0 and F0, we have that any triangulation of the union is the union of triangulations of P and P0. The polyhedron P was constructed so that the dihedral angles corresponding to the edges EB and FD are concave, therefore the diagonals AF and EC lie outside of P. It is easy to see that the triangles ABC and ACD cannot be faces of disjoint tetrahedra contained in P, thus diagonal BD must be an edge of at least one tetrahedron in any triangulation of P. A similar argument applied for P0 gives that the diagonal AC is an edge of at least one tetrahedron in any triangulation of P0. Thus the union of P and P0 is not triangulable. and Example 9 Start with a unit cube with faces labeled Top, Bottom, Left, Right, Front, and Back and translate the Top to the right by a distance greater than 1. Label the vertices as in Figure 3.4. Move vertices W and Y along the lines AW and CY respectively up by and vertices X and Z along the line XZ away from one another by . Now let P be the polyhedron 24 Figure 3.3: A non-triangulable polyhedron which can be tiled with tetrahedra bounded by the square ABCD and the ten triangles ABW, BWX, BXY, BCY, CDY, DYZ, DWZ, ADW, WXZ and XYZ. A B CD W X YZ Figure 3.4: Labeling the translated cube Finally let P0 be the image of P under the rotation of 180o about the line through the midpoints of AD and BC. Label the images of W, X, Y, and Z as W0, X0, Y0, and Z0 respectively. First notice that P is triangulable as it is the union of the tetrahedra ABDW, BWXZ, BCDY, BDWZ, BDYZ and BXYZ. Since the same holds for P0 we have that the union of P and P0 can be tiled by tetrahedra. Next we show that the union of P and P0 is not triangulable. Since the vertices W, X, Y, nor Z cannot see the vertices W0, X0, Y0, and Z0, we have that any triangulation of the union is the union of triangulations of P and P0. The polyhedron P was constructed so that the dihedral angles corresponding to the edges BW, BY, DW, and DY are concave, therefore the diagonals AX, AZ, CX, and CZ lie outside of P. 25 Assume the triangles ABC and ACD are faces of disjoint tetrahedra contained in P, then the fourth vertex of each tetrahedra respectively is W or Y. Since the tetrahedra ABCW and ACDY do not intersect along a common face, but do intersect in a plane, they cannot both be in the triangulation. A similar argument is made for ABCY and ACDW, therefore the fourth vertex of the tetrahedra containing ABC and ACD respectively is the same. By symmetry let?s assume ABCW and ACDW are tetrahedra of the triangulation. The tetrahedron containing XYZ as a face either has vertex B or D as its fourth vertex, but XYZB and XYZD intersect both ABCW and ACDW. Therefore diagonal AC cannot be an edge of a tetrahedron in a triangulation of P, so diagonal BD must be an edge of at least one tetrahedron in any triangulation of P. A similar argument applied for P0 yields that the diagonal AC is an edge of at least one tetrahedron in any triangulation of P0. Therefore the union of P and P0 is not triangulable. Remark 4. A non-triangulable polyhedron is tilable only if it contains at least four coplanar vertices where no three are incident with a common face. Since SCn does not contain 4 coplanar points, for su ciently small , where no three are incident with a common face, Remark 4 implies that no tiling exists. Throughout the remainder of the text, we will often look at tetrahedra contained inside a polyhedron and determine if any two interior tetrahedra intersect. If two tetrahedra intersect in more than a plane, we can conclude that both tetrahedra cannot be in a tiling by tetrahedra. Lemma 3.2. Let two tetrahedra TO and TB share an edge e and contain two coplanar faces tO and tB respectively on a plane P. If there exists a plane Q6= P containing e such that the fourth vertex O of TO is in the open halfplane bounded by Q containing tB and the fourth vertex B of TB is in the open halfplane bounded by Q containing tO, then TO and TB overlap. 26 Figure 3.5: Intersecting tetrahedra Lemma 3.2 can simply be proven by noticing that the interior dihedral angle of TO at e and the interior dihedral angle of TB at e sum to greater than 180o. Since each face of a tetrahedron t2T is a triangle, we say T induces a surface trian- gulation. Rambau used this observation in proving Corollary 2.10 by using Theorem 2.9. We will also use this observation when considering which tetrahedron a particular surface triangle belongs. De nition 7. An ear is a triangle in a triangulation of a polygon P with exactly two of its edges being edges of P. The vertex incident with these two edges will be the ear vertex. Theorem 3.3. (Meisters [17]) For n > 3, every triangulation of a polygon has at least 2 ears. It is common to view each triangulation as a tree by letting each triangle be represented by a dual vertex where two dual vertices are adjacent if the corresponding triangles share an edge. In this dual tree each ear is a leaf. We will borrow the terminology of pruning a leaf, to prune ears of a triangulation. 27 De nition 8. An ear E is pruned by deleting the ear from the triangulation, leaving the edge which was not an edge of P as an edge of P0 = P E. In doing so, we delete the ear vertex from the polygon. 3.3 Non-Tilable Polyhedra De nition 9. We construct a polyhedron which will have two horizontal faces (bottom base and upper base) and several side faces. Let the bottom base be a convex polygonn Cn on n vertices labeled clockwise as b1;b2;:::;bn. De ne li to be the line containing edge bibi+1 (indices taken modulo n). Now we will call the closed area bounded by the lines li, li 1, and li 2, which contains bi 1bi but does not contain Cn, region Ri (Figure 3.6). (Region Ri may be in nite if li and li 2 are parallel or intersect on the same side of li 1 as the polygon.) Now de ne the upper base as the convex polygon Un = convfui;u2;:::;ung, where ui2Ri. Let B0Cn = convf(Cn f0g) [ (Un f1g)g, and BCn (Figure 3.7) = B0Cn convf(bi,0),(bi+1,0),(ui+1,1),(ui+2,1)g, for all i2f1;2;:::;ng taken modulo n. Cn b1 b2 b3 b4 b5 b6 b7 l2 l1 l3 l4 l5 l6l 7R2 R 1 R3 R4 R5 R 6 R7 Figure 3.6: All regions Ri for C7 Theorem 3.4. The non-convex polyhedron BCn cannot be tiled with tetrahedra. 28 b1 b2 b3 b4 b5 b 6 b7u1u2 u3 u4 u5 u6 u7 Figure 3.7: Polyhedron BC7 Proof Assume a set of simplices (tetrahedra) S tiles BCn. The tiling by S induces a triangulation of (Un f1g), which we will call T. Now, for every t2T there exists exactly one s2S such that t is a face of s. Obviously, the fourth vertex of s must be a vertex of (Cn f0g). De ne a sub-polygon to be the convex hull of a subset of the vertices of a polygon. Let P be the set of sub-polygons of Un such that every edge of a sub-polygon p2P is an edge of some t2T. Let e be an edge of p and let t be a triangle of T having e as an edge and inside p. We will say p is a separator if every point bi in the open halfplane, bounded by the line containing e, which does not contain p cannot be in a tetrahedron of S with t as a face. Let P0 P so that every p02P0 is separating. P0 is not empty since Un is a separating sub-polygon. A minimal separating sub-polygon is a sub-polygon with the fewest vertices. Let m2P0 be a minimal separating sub-polygon with n vertices. If n> 3, then there is a 29 t2T which is an ear of m. Let d be the edge of t which is not an edge of m. Observe that there exists a triangle t02T which has d as an edge and is contained in m. Remark 5. The construction of Un yields the property that the line containing the diagonal uiuj (for i < j) bounds two open halfplanes such that the halfplane containing the vertices uk for i 0, the non-convex twisted prism SCn cannot be triangulated. Proof It su ces to show that for any Cn, there exists a su ciently small such that for any diagonal (vi;1)(vj;1) (for i 3? It follows from the proof of Theorem 3.8 that for n = 3 or 4, the non-convex twisted pentaprism cannot be tiled. However, for arbitrarily n, the regular n-gon has many non- isomorphic triangulation, thus a more sophisticated method is needed. 40 Chapter 4 Extendable Surface Triangulation In the previous chapter we discussed triangulable or tilable polyhedra while alluding to surface triangulations. We wish to formalize the relationship between these concepts. De nition 12. A surface triangulation of a given polyhedron is called extendable to a triangulation (to a tiling respectively) if the polyhedron has a triangulation (tiling respectively) such that each triangle of the surface triangulation is a face of one of the participating tetrahedra. In this case we also say that the set of tetrahedra which triangulate (or tile respectively) the polyhedron induces the given surface triangulation. It is hard to tell which chain of thinking led the di erent authors to construct their non- triangulable polyhedra (Examples 1-6), however a close look at the polyhedra can reveal some common key features which lead to further non-triangulable polyhedra. If one starts with a speci c symmetrical convex polyhedron and nds a non-extendable surface triangulation, then there might be a chance that one can perturb the vertices of the polyhedron so that the new polyhedron is non-triangulable. We will make this perturbing idea more precise. Theorem 4.1. There is a su eciently small so that an perturbed surface triangulation is triangulable if and only if the surface triangulation is extendable to a triangulation. The proof of Theorem 4.1 hinges solely of the fact that the set of tetrahedra are joined face-to-face. It is natural to assume the analogous holds true for extending surface trian- gulations to a tiling by tetrahedra. However, we notice that the tetrahedra are not joined face-to-face in a tiling and thus the analogue is not true. Theorem 4.2. There exist extendable surface triangulations to a tiling by tetrahedra, where an perturbation of the surface triangulations is non-tilable. 41 Remark 10. A polyhedron with only triangular faces is a perturbation of itself, thus if tilable then there is a polyhedra which it is an perturbed surface triangulation which is extendable. Proof The simplest example of such a formation is to consider the tiling of a cube shown in Figure 4.1. Since the cyclic diagonals are a subset of the induced surface triangulation, then the perturbation of the twist described by Rambau [20] would produce a corresponding tiling, yet Theorem 3.4 showed that the twisted cube is not tilable. Dissectthecubedownthediagonalplane. Triangulateeachpiecesothatits dotteddiagonalisused. Figure 4.1: Tiling of a cube So we ask, why is this so? We will assume we have an extended tiling of the surface triangulation of cyclic diagonals on the cube. Notice that the bottom face is triangulated into two triangles which must be connected to two opposing vertices of the top face as shown by the two tetrahedron in Figure 4.2. It is obvious by Lemma 3.2 that the two tetrahedra will overlap for any small twist. 42 Figure 4.2: Extended tiling which crosses 4.1 Realizing Surface Triangulations Let us discuss a perturbation in a planar setting. Assume a given polygon P has its edges partitioned into line segments by placing new vertices along the edges. Some (or all) edges may contain no new vertices, thus not partitioned. The introduction of new vertices will result in a degenerate polygon, where some pairs of adjacent edges are collinear. Let > 0 be a su ciently small positive number. Making a degenerate polygon semi-concave is to transform (Figure 4.3) its vertices so that the vertices are repositioned within their neighborhood and all degenerate internal angles (180o) of the given polygon become concave. If no new vertices are added in the partitioning, then there is no need to move any of the vertices. Otherwise one can get a desired semi-concave polygon by replacing each edge of P with a slightly bent concave polygonal arc with the new vertices from that edge. One can say that the role of the su ciently small in the above de nition is the same as saying one wants to perturb the vertices slightly. The R3 variant of this problem is less trivial and not an analogue of the above de nition as we will not add new vertices to edges, but rather new edges on the faces of a polyhedron. Let us start with a proper de nitions: 43 Figure 4.3: Transforming a degenerate polygon into a semi-concave polygon De nition 13. Let ^P be a surface triangulation of a given polyhedron P. ^P can be viewed as a degenerated polyhedron. Let > 0 be a su ciently small positive number. Making a degenerate polyhedron semi-concave is to transform its vertices so that the vertices are repositioned within their neighborhood and the dihedral angles between coplanar adjacent faces become concave. The resulting polyhedron will be called the realized semi-concave polyhedron of the surface triangulation of P. We will also refer to the transformation as realizing a surface triangulations. Theorem 4.3. If each vertex of a convex polyhedron is adjacent to no more than three non- triangular faces, then every surface triangulation of the polyhedron can be realized. Proof Let P be the convex polyhedron satisfying the conditions of Theorem 4.3 and let ^P be a surface triangulation of P. Recall P is the set of diagonals of the surface triangulation. Color all the triangular faces of P blue, and every triangle of ^P red (except those which are faces of P). Also color every edge of P black and every diagonal of P white. Consider the degenerate polyhedra bounded by the blue and red triangles; the interior dihedral angle at every white edge is 180o and every blue triangular face is bounded by three black edges, whose dihedral angles are convex. 44 It is easy to see that there exist a su ciently small so that dragging any vertex of P along with its incident edges to a point inside an neighborhood will result in all the convex dihedral angles remaining convex, and the concave dihedral angles remaining concave. Let v be a vertex of P such that it is an ear vertex (De nition 7) of at least one of the faces triangulated by ^P. The dihedral angles corresponding to the white edge of an ear can become convex or concave depending on the perturbation of its ear vertex. Our job is to nd a perturbation which makes the dihedral angles of the white edge concave. We will distinguish between two cases: Case 1: If vertex v is an ear vertex on every non triangular incident face: Let v be the ear vertex of ears E1, E2 and E3 on faces F1, F2 and F3 respectively. (If fewer than three non triangular faces exist, disregard the extra ears and faces.) We will drag v along with its incident edges of P to a point inside of the neighborhood of v which is not coplanar with F1, F2 or F3. Furthermore we will pick the point so that each white edge of E1, E2, and E3 becomes concave. Each plane containing Fi bounds two hemispheres of the neighborhood of v, one which contains all the points which if v is dragged to will make the white edge of Ei a concave interior angle and the other contains the points which will make a convex interior angle. All three faces contain v, so the intersection of the hemispheres causing concave interior angles at the white edges is not empty, thus such a point exists. Case 2: If vertex v is not an ear vertex of at least one of its non triangular incident faces. Assume v is not an ear vertex of the non triangular faces F1 and F2. (If only one non triangular faces exist, disregard F2) We will drag v along with its incident edges of P to a point inside of the neighborhood of v which is coplanar with F1 and F2 and causes the white edge of every ear, where v is an ear vertex, to become concave. The line which is the intersection of the planes containing F1 and F2 contains such a point. Notice every white edge along F1 and F2 remains degenerate. 45 In both cases, change the color of the white edge(s), which are now concave, to black and the red ear(s), which are now faces, to blue. The new polyhedra (possibly still degenerate) has at least one less red triangle and at least one less white edge. This implies that the above process, beginning with choosing a vertex v which is incident to a red ear, can be repeated nitely many times resulting with a polyhedron with only blue triangular faces and concave dihedral angles at each of the original diagonals of P. Remark 11. With the process shown in Theorem 4.3, each diagonal along a face P which crosses a diagonal of P becomes outside the realized polyhedron. 4.2 Polyhedra with Regular Polygonal Faces We will now attempt to nd non-extendable surface triangulations where the realized semi-concave polyhedron is a non-triangulable polyhedron. We will begin our search by investigating the surface triangulations of polyhedra composed of regular polygonal faces, since each meets the conditions of Theorem 4.3 Platonic Solids and Prisms Theorem 2.9 clearly de ned a partial surface triangulation of the right prism which cannot be extended. Theorem 4.4. The 5 Platonic solids are divided into two classes depending on the extendibil- ity of their surface triangulations: A) Every surface triangulation is extendable to a triangulation. B) There exist at least one surface triangulation which is not extendable to a triangulation. Proof It is obvious that there is only one surface triangulation of the regular tetra- hedron, octahedron, and icosahedron, which is the empty set of diagonals, thus the surface triangulation of each of these is extendable. However, we have discussed in length the state- ment of Theorem 2.9 showing the surface triangulation of the cyclic diagonals of a prism is not extendable, therefore there exists a surface triangulation of the cube (and every right 46 prism) which is not extendable. With the relationship given in Theorem 4.1, we can also conclude from Theorem 3.8 that the surface triangulation of the regular dodecahedron which can be realized to DH( ) is not extendable. Archimedean and Johnson Solids We will explicitly study the surface triangulations of the Archimedean solids. We have provided the names, vertex labeling and an image (taken from http:==en.wikipedia.org=wiki= Archimedean solid) of each Archimedean Solid. As a bi-product, we will mention results concerning some Johnson solids. Theorem 4.5. The 13 Archimedean solids are divided into four classes depending on the extendibility of their surface triangulations: A) Every surface triangulation is extendable to a triangulation. B) Every surface triangulation can be extended to a tiling by tetrahedra, but it is unknown if each surface triangulation can be extended to a triangulation. C) There exist at least one surface triangulation which is not extendable to a triangulation. D) It is unknown if each surface triangulation can be extended to a triangulation. 47 Class A 1. Snub cube (3,3,3,3,4) 2. Snub dodecahedron (3,3,3,3,5) 3. Cuboctahedron (3,4,3,4) De nition 14. A fan is a triangulation such that all simplices contain a common vertex. We will call the common vertex the fan vertex. Remark 12. To show that all convex polyhedra contain a triangulation it is su cient to create a fan at one of the vertices. In a fan triangulation of a convex polyhedron, we notice that the triangulation induces a fan triangulation at that vertex on every adjacent face. Proof of Class A If a surface triangulation of a convex polyhedron contains a vertex which is a fan of each of its adjacent faces, then by Remark 12 it is extendable. A fan triangulation is the set of all tetrahedra created by taking the three vertices of every triangle of the surface triangle, except those containing the fan vertex, and adjoining it with the fan vertex. Since each triangulation of a quadrilateral and pentagon are fans we will rst consider the Archimedean solids which only contain triangles, squares, and pentagons. Not all such polyhedra with this property must be triangulated with a fan vertex, but if every square and pentagon is only adjacent to triangular faces, then every surface triangulation contains a fan vertex. The snub cube and snub dodecahedron have this property, thus belong to class A. It is worth noting that there are forty four Johnson solids which have this property. You can nd a list of these Johnson solids in the appendix. 48 Although the cuboctahedron has previously been shown to be in class A [7], Figure 4.4 shows the only unique surface triangulation without a fan vertex. It would su ce to nd the extension of this surface triangulation, however, we wish to present a new method of nding an extension of all surface triangulation simultaneously. 1 2 3 45 6 2 1 6 54 3 TopView BottomView T2 T 4 T6 T5 T3 T1 Figure 4.4: Vertex labeling of the cuboctahedron Consider the vertices labeled as in Figure 4.4 and remove the convex hull of the point setfT1;T2;T3;T4;T5;T6g, which is a triangular anti-prism. Now we can break the remaining volume into the six congruent pieces which are the convex hulls of points setsf1,2,T2,T3,T4g, f2,3,T3,T4,T5g, f3,4,T4,T5,T6g, f4,5,T1,T5,T6g, f5,6,T1,T2,T6g, and f1,6,T1,T2,T3g. Notice each piece is connected to two others by common triangles, also each shares a triangular face with the anti-prism. Now we should notice that the six congruent pieces all have ex- actly one square face from the exterior of the cuboctahedron, so they can be triangulated with either diagonal of the square and by the fan argument each surface triangulation is extendable. Class B 4) Rhombicuboctahedron (3,4,4,4) Proof of Class B 49 Remark 13. If we want to tile a polyhedron, it su ces to slice the shape by a plane(s) which creates no new vertices and consider tiling the remaining pieces. The issue with this method when attempting to triangulate the polyhedron is that the triangulation of each piece must induce the same surface triangulation on the cross section. First observe that on the rhombicuboctahedron there are three sets of cyclic squares, where each is the convex hull of a octagonal prism. Also notice each pair of cyclic squares intersect on two opposing parallel faces. We will attempt to break the rhombicuboctahedron into three pieces by removing one of these octagonal prisms as shown in Figure 4.5. Figure 4.5: Slicing the rhombicuboctahedron Before doing this we must rst show that each piece can be tiled by tetrahedra. So by Theorem 3.4 we need that the octagonal prism not be surface triangulated by the cyclic diagonals. Since there are three of these it is easily seen that all three cyclic squares cannot be triangulated by cyclic diagonals simultaneously, thus every surface triangulation will contain at least one octagonal prism not containing the cyclic diagonals along its lateral faces. Therefore we can cut the rhombicuboctahedron as shown in Figure 4.5 and tile each piece with tetrahedra. It is obvious that this method does not provide a triangulation of the rhombicubocta- hedron since either octagonal cut may contain di erent triangulations on its cross sections, yet if we can show that every surface triangulation of the square cupola (the top and bottom 50 pieces in Figure 4.5) can be extended, then we will be able to triangulate each octagonal cross section in the same manner. Open Problem Is every surface triangulation of a square cupola extendable to a triangulation? Remark 14. This will also prove that each surface triangulation of the square orthobicupola and square gyrobicupola is extendable.(Notice this is not the case for the elongated square gyrobicupola. Although it can be broken into three pieces as the rhombicuboctohedron, the octagonal prism may be triangulated on the surface by the cyclic diagonals.) Class C 5)Truncated tetrahedron (3,6,6) 6) Truncated cube (3,8,8) 7) Truncated dodecahedron (3,10,10) 8) Icosidodecahedron (3,5,3,5) Proof of Class C For the truncated tetrahedron, we consider the partial surface triangulation of three hexagonal faces shown in Figure 4.6. Notice the top face is a trianglef1,2,3gand the bottom face is a hexagonfA,B,C,D,E,Fg, and the other three vertices are labeled by there adjacent vertices. 51 A B C DE F 1 23 AB1 CD2EF3 Figure 4.6: Edge graph of a partial surface triangulation of the truncated tetrahedron We will again consider the abstract case, and show no tiling by tetrahedra induces such a surface triangulation. Now let us focus on the surface triangle fB,C,1g. If we assume a tiling by tetrahedra exists, we can consider which vertex will be in a tetrahedron with trianglefB,C,1g. It is obvious the the verticesfA,F,2,AB1,CD2gare not the fourth vertex. Now if we prescribe a surface triangulation on the bottom hexagon fA,B,C,D,E,Fg which contains diagonal AC or CF, the triangle fB,C,1g must be a face of tetrahedra fB,C,1,3g in the tiling (or triangulation) of the truncated tetrahedron. Now we can form a similar argument that the surface triangle fD,E,2g must belong to the tetrahedra fD,E,1,2g by prescribing a surface triangulation contain diagonal CE. Now we reach a contradiction as tetrahedra fB,C,1,3g and fD,E,1,2g overlap. Therefore any surface triangulation containing the diagonals B1, C1, (CD2)1, D2, E2, (EF3)2, (AB1)3, CE and AC or CF cannot be extended. Similar arguments can be made for the other three polyhedra in this class. In each polyhedron we use a similar technique of investigating triangles from a surface triangulation 52 which are all adjacent to a common triangular face and use diagonals on other faces to force which tetrahedra contains the surface triangles incident with the common triangular face. An edge graph for such a surface triangulation of the truncated cube is provided in Figure 4.7. (We will not provide the diagram of the truncated dodecahedron or the icosidodecahedron, because it looses its visual appeal with the distortion needed to draw the faces in an edge graph.) We have color coded the diagram so that each face diagonal (dotted curves) restricts vertices that can be in a tetrahedron with the corresponding colored face triangle. We have also colored each vertex to show it can be in a tetrahedron with the triangle of the same color. The crux of the argument is to recognize that no two of the given colored triangles can both be in a tetrahedron with another vertex from their shared triangular face. Then we arbitrarily choose two of the colored triangles to be in a tetrahedron with a fourth vertex elsewhere, and nd that any combination of their fourth vertices respectively will cause the two tetrahedra to overlap. Figure 4.7: Edge graph of a partial surface triangulation of the truncated cube Obviously we need to consider more surface diagonals in the cases of the truncated dodecahedron and the icosidodecahedron. 53 Class D 9) Truncated octahedron (4,6,6) 10) Great rhombicuboctahedron (4,6,8) 11) Truncated icosahedron (5,6,6) 12) Rhombicosidodecahedron (3,4,5,4) 13) Great rhombicosidodecahedron (4,6,10) These polyhedra cannot be broken into smaller shapes to be triangulated, since their is no plane cutting the polyhedron into two pieces without creating new vertices. The cyclic surface triangle method shown for class C also does not seem to work as the rhombicosi- dodecahedron is the only shape containing triangular faces, and it seems as if having more than three non-triangular faces adjacent to a triangular face will hinder the contradiction reached with the other four polyhedra where this technique proved fruitful. 54 Bibliography [1] F. Bagemihl, On indecomposable polyhedra, American Math. Monthly 55, (1948), 411- 413. [2] A. Below, J.A. De Loera and J. Richter-Gebert, Finding minimal triangulations of con- vex 3-polytopes is NP-hard, Preceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, (San Francisco 2000), ACM, New York, (2000), 65-66. [3] M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications, Third Edition, Springer, (2008). [4] P. Brass, W. Moser and J. Pach, Research Problems in Discrete Geometry, Springer, 2005. [5] B. Chazelle, Convex partitions of polyhedra: a lower bound and worse-case optimal algorithm, SIAM Journal of Computation 13, No. 3, (1984), 488-507. [6] B. Chazelle and L. Palios, Triangulating a nonconvex polytope, Discrete and Computa- tional Geometry 5, (1990), 129-138. [7] J.A. De Loera, J. Rambau and F. Santos, Triangulations: structures for algorithms and applications, Algorithms and Computation in Mathematics 25, Springer, 2010. [8] S. Devadoss and J. O?Rourke, Discrete and Computational Geometry, Princeton Uni- versity Press, 2011. [9] H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, New York, 1987. [10] L. Fejes T oth, Regular Figures, Pergamon Press, New York, 1964. [11] L. Fejes T oth, Lagerungen in der Ebene, auf der Kugel und im Raum, Second Edition, Springer-Verlag, New York, 1972. [12] J.E. Goodman and J. Pach, Cell decomposition of polytopes by bending, Israel J. Math. 64, 1988, 129-138. [13] B. Jessen, Orthogonal icosahedron, Nordisk Mat. Tidskr. 15, (1978), 165-170. [14] C. Lawson, Transforming triangulations, Discrete Math. 3, (1972), 365-372. [15] N.J. Lennes, Theorems on the simple nite polygon and polyhedron, American Journal of Mathematics 33, (1911), 37-62. 55 [16] J. O?Rourke, Computational Geometry in C, Second Edition, Cambridge University Press, 1998. [17] G.H. Meisters, Polygons have ears, American Mathematical Monthly, (June/July 1975),(648-651). [18] J. Pach and P.K. Agarwal, Comdinatorial Geometry, A Wiley-Interscience Publication, New York, 1995. [19] M. S. Paterson and F.F. Yao, Binary partitions with applications to hidden-surface removal and solid modeling, Proc. 5th ACM Symp. Comp. Geom., (1989), 23-32. [20] J. Rambau, On a generalization of Sch onhardt?s polyhedron, Combinatorial and Com- putational Geometry 52, (2005), 501-516. [21] C.A. Rogers, Packing and Covering, Cambridge University Press, New York, 1964. [22] J. Ruppert and R. Seidel, On the di culty of triangulating three-dimensional nonconvex polyhedra, Discrete and Computaional Geometry, 7 issue 3, (1992), 227-253. [23] D.D. Sleator, R.E. Tarjan and W.P. Thirston, Rotation distance, triangulations, and hyperbolic geometry, Journal of the AMS, 1, (1988), 647-681. [24] E. Sch onhardt, Uber die Zerlegung von Dreieckspolyedern in Tetraeder, Mathematics Annalen 89, (1927), 309-312. 56 Appendices 57 Appendix A Johnson Solids Containing Fan Vertices in every Surface Triangulation 1. Square Pyramid 2. Pentagonal Pyramid 3. Elongated Triangular Pyramid 4. Elongated Square Pyramid 5. Elongated Pentagonal Pyramid 6. Gyroelongated Square Pyramid 7. Gyroelongated Pentagonal Pyramid 8. Triangular Dipyramid 9. Pentagonal Dipyramid 10. Elongated Triangular Dipyramid 11. Elongated Square Dipyramid 12. Elongated Pentagonal Dipyramid 13. Gyroelongated Square Dipyramid 14. Gyroelongated Triangular Cupola 15. Gyroelongated Square Cupola 16. Gyroelongated Pentagonal Cupola 17. Gyroelongated Triangular Bicupola 18. Gyroelongated Square Bicupola 19. Gyroelongated Pentagonal Bicupola 20. Gyroelongated Pentagonal Cupolaro- tunda 21. Augmented Triangular Prism 22. Biaugmented Triangular Prism 23. Triaugmented Triangular Prism 24. Augmented Pentagonal Prism 25. Biaugmented Pentagonal Prism 26. Augmented Hexagonal Prism 27. Parabiaugmented Hexagonal Prism 28. Metabiaugmented Hexagonal Prism 29. Triaugmented Hexagonal Prism 30. Augmented Dodecahedron 31. Parabiaugmented Dodecahedron 32. Metabiaugmented Dodecahedron 58 33. Triaugmented Dodecahedron 34. Metabidiminished Icosahedron 35. Tridiminished Icosahedron 36. Augmented Tridiminished Icosahedron 37. Snub Disphenoid 38. Snub Square Antiprism 39. Sphenocorona 40. Augmented Sphenocorona 41. Sphenomegacorona 42. Hebesphenomegacorona 43. Disphenocingulum 44. Triangular Hebesphenorotunda 59