����������� ������ 57 (2005), 1–9

UDK 514.122

���������� ������ ��� research paper

ALGORITHMS FOR TRIANGULATING POLYHEDRA INTO A SMALL NUMBER OF TETRAHEDRA

Milica Stojanović

Abstract. Two algorithms for triangulating polyhedra, which give the number of tetrahedra depending linearly on the number of vertices, are discussed. Since the smallest possible number of tetrahedra necessary to triangulate given polyhedra is of interest, for the first–“Greedy peeling” algorithm, we give a better estimation of the greatest number of tetrahedra (3n − 20 instead of 3n − 11), while for the second one–“cone triangulation”, we discuss cases when it is possible to improve it in such a way as to obtain a smaller number of tetrahedra.

1. Introduction

It is known that it is possible to divide any polygon with n − 3 diagonals into n − 2 triangles without gaps and overleaps. This division is called triangulation. Many different practical applications require computer programs, which solve this problem. Examples of such algorithms are given by Seidel [8], Edelsbrunner [4] and Chazelle [2]. The most interesting aspect of the problem is to design algorithms, which are as optimal as possible.

The generalization of this process to higher dimensions is also called a triangulation. It consists of dividing polyhedra (polytope) into tetrahedra (simplices). Besides fastness of algorithm, there are new problems in higher dimensions. It is proved that it is impossible to triangulate some of nonconvex polyhedra [7, 9] in a three-dimensional space, and it is also proved that different triangulations of the same polyhedron may have different numbers of tetrahedra. Considering the smallest and the greatest number of tetrahedra in triangulation (the minimal and the maximal triangulation), these authors obtained values, which linearly, resp. squarely depend on the number of vertices. Interesting triangulations are described in the papers of Edelsbrunner, Preparata, West [5] and Sleator, Tarjan, Thurston [10]. Some characteristics of triangulation in a three-dimensional space are given by Lee in [6] and this problem is also related to the problems of triangulation of a set of points in a three-dimensional space [1, 5] and rotatory distance (in a plane) [10].

AMS Subject Classification: 52C17, 52B05, 05B40

Keywords and phrases: Triangulation of polyhedra, minimal triangulation.

In this paper in Section 2 we describe some polyhedra with n vertices, which are possible to triangulate into n − 3 or n − 2 tetrahedra. In Sections 3 and 4 we give some observations about two algorithms for triangulation of polyhedra, which can give the number of tetrahedra that linearly depends on the number of vertices. We consider convex polyhedra in which each 4 vertices are noncoplanar and all faces are triangular. Furthermore, all considered triangulations are face to face. The number of edges from the same vertex will be called the order of vertex. For triangulation in an n-dimensional space we will also use the term n-triangulation.

2. Some examples of polyhedra and their triangulations

It is possible to triangulate all convex polyhedra, which is not the case with nonconvex ones. An example of a nonconvex polyhedron, which is impossible to triangulate, was given by Schonhardt [9] and referred to in [7]. This polyhedron is obtained in the following way: triangulate the lateral faces of a triangular prism A_{1}B_{1}C_{1}A_{2}B_{2}C_{2} by the diagonals A_{1}C_{2}, B_{1}A_{2} and C_{1}B_{2} (Fig. 1.). Then “twist” the top face A_{2}B_{2}C_{2} by a small amount in the negative direction. In such a polyhedron none of tetrahedra with vertices in the set {A_{1}, B_{1}, C_{1}, A_{2}, B_{2}, C_{2}} is inner, so the triangulation is not possible.

Fig. 1

Let us now consider triangulations of a bipyramid with a triangular basis ABC and apices V_{1} and V_{2} (Fig. 2.). There are two different triangulations of this kind. The first one is into two tetrahedra V_{1}ABC and V_{2}ABC, and the second one is into three: V_{1}V_{2}AB, V_{1}V_{2}BC and V_{1}V_{2}CA.

It is proved that the smallest possible number of tetrahedra in the triangulation of a polyhedron with n vertices is n − 3. But, it is not possible to triangulate each polyhedron into n − 3 tetrahedra. For example, all the triangulations of an octahedron (6 vertices) give 4 tetrahedra, what is the reason to mention examples of polyhedra for which triangulation with n − 3 vertices is possible.

The pyramids with n − 1 vertices in the basis (i.e., a total of n vertices) are triangulable by doing any 2-triangulation of the basis into (n − 1) − 2 = n − 3 triangles. Each of these triangles makes with the apex one of tetrahedra in 3triangulation. If the basis of a “pyramid” is a space polygon, then it is possible to triangulate it in a similar way without taking care about convexity and this will be used in the algorithm in Section 3.

Let us return to the two methods of triangulating a bipyramid, but this time with n − 2 vertices in the basis (which can also be a space polygon). If we divide it into two pyramids and triangulate each of them with taking care of a common 2-triangulation of the basis, then we will obtain 2(n − 4) tetrahedra. In the second

Fig. 2

method each of n − 2 tetrahedra has a common edge joining the apices of the bipyramid and, moreover, each of them contains a pair of the neighbour vertices of the basis (i.e., one of the edges of the basis). For n = 5 (a bipyramid with a triangular basis) it has been found that the first method is “better”, i.e., it gives a smaller number of tetrahedra. For n = 6 (the octahedron) both methods give 4 tetrahedra and for n ⩾ 7 the second method is “better”.

3. The “Greedy Peeling” triangulation

The “Greedy Peeling” (GP) algorithm for triangulating a given polyhedron P is iterative and is described below.

Take a vertex of the smallest order (an arbitrary one in the case that there are more such vertices) and discard the triangulated “pyramid” which consists of the mentioned vertex and its neighbour vertices. 2-triangulate the new surface of the remaining polyhedron in such a way that the whole triangulation would be face to face. All this has to be done in such a way to get a new polyhedron, which is convex. Then repeat everything with the new polyhedron. At the end of such triangulation there remains only one tetrahedron.

This algorithm is described in [5] for a more general case of triangulating a set of n points in the space. It is estimated that in the GP triangulation of a polyhedron with n vertices there are no more than 3n − 11 tetrahedra. This value is obtained on the basis of a consequence of Euler’s theorem [3, 4], by which each polyhedron contains at least one vertex of order not greater than 5. Since discarding a vertex of order k gives k − 2 tetrahedra and the last four vertices make one tetrahedron, the upper bound of the number of tetrahedra in this triangulation is 3n − 11.

For getting a better estimation, let us observe that it is possible to determine the smallest order of vertex more precisely.

Lemma 3.1. Polyhedra with 5 vertices have at least one vertex of order 3; polyhedra with n vertices, 6 ⩽ n ⩽ 11 have at least one vertex of order not

greater than 4;

polyhedra with n ⩾ 12 vertices have at least one vertex of order not greater than 5.

Proof. Let n be the number of vertices, e of edges and f of faces. Then, by Euler’s theorem [3, 4] for a polyhedron whose faces are triangular, e = 3n−6 holds.

The mean number of edges in each vertex is m = \frac{2e}{n} = \frac{6n − 12}{n} = 6 − \frac{12}{n}. Since for n = 5, it is m < 4, for 6 ⩽ n ⩽ 11, it is m < 5, and for n ⩾ 12, it is m < 6, our statement follows.

Lemma 3.2. Each polyhedron with 13 vertices has at least one vertex of order not greater than 4.

Proof. If we suppose the opposite, then the polyhedron has one vertex V of order 6 and 12 vertices of order 5. This vertex V is connected with vertices A, B, C, D, E, F (of order 5). Besides being connected with V, these 6 vertices are interconnected so as to form a space hexagon, i.e., each is connected with 2 further vertices. For each of these vertices there are 2 edges more joining it with new vertices. Since the faces are triangular, those 12 edges build 6 new faces with vertices A, B, C, D, E, F and 6 vertices more—A_{1}, B_{1}, C_{1}, D_{1}, E_{1}, F_{1}. After the application of any 2-triangulation of the (space) hexagon A_{1}B_{1}C_{1}D_{1}E_{1}F_{1}, some of vertices A_{1}, B_{1}, C_{1}, D_{1}, E_{1}, F_{1} will be left as a 4-order vertex.

With the previous we have proved the following

Theorem 3.1. The greatest number of tetrahedra in a GP triangulation of a polyhedron with n vertices is not greater than T_{n} where:

• T_{n} = n − 3 for n = 4, 5;

• T_{n} = 2n − 8 for 6 ⩽ n ⩽ 11;

• T_{12} = 17;

• T_{n} = 3n − 20 for n ⩾ 13.

If there are more vertices of the same, the smallest order, then by a suitable choice of the order of vertices to be discarded in the steps of the GP algorithm, it is possible to get a smaller number of tetrahedra. But, the previous estimation cannot be better, since for the given n there exists a polyhedron with n vertices, such that for its GP triangulation T_{n} is tight. According to this, let us prove:

Theorem 3.2. (1) There is a GP triangulation of icosaedron into 17 tetrahedra;

(2) There is such a series of polyhedra with n ⩾ 14 vertices of order not less than 5 and such a GP triangulation of these polyhedra, which in each iteration gives the polyhedron from the same series, but with one vertex less.

Fig. 3

Proof. (1) Denote by V_{1} and V_{2} the opposite vertices of an icosaedron and by A_{1}, B_{1}, C_{1}, D_{1}, E_{1} and A_{2}, B_{2}, C_{2}, D_{2}, E_{2} the vertices of space pentagons connected with V_{1}, resp. V_{2}, and chosen in such a way that the icosaedron contains edges A_{1}A_{2} and A_{1}B_{2}. We obtain a GP triangulation into 17 tetrahedra if we discard the vertices in the following order and add new edges denoted in parentheses:

A_{1} (V_{1}A_{2}, V_{1}B_{2}), B_{1} (V_{1}C_{2}), C_{1} (V_{1}D_{2}), D_{1} (D_{2}E_{1}), E_{1} (V_{1}E_{2}), E_{2} (A_{2}D_{2}), V_{1} (A_{2}C_{2}), B_{2}. There remains the tetrahedron A_{2}C_{2}D_{2}V_{2}.

(2) First we will introduce the basic series of polyhedra with n = 6k+2 (k ⩾ 2) vertices of order not less than 5 and then add, according to the GP algorithm, polyhedra with n vertices, 6(k − 1) + 2 < n < 6k + 2 (k ⩾ 3), with the same property.

The polyhedra from the basic series are obtained as follows: k space hexagons A_{i}B_{i}C_{i}D_{i}E_{i}F_{i} (1 ⩽ i ⩽ k) are connected in such a way that the polyhedron contains edges A_{i}A_{i+1} and A_{i}F_{i+1} (1 ⩽ i ⩽ k − 1) and vertices of hexagons A_{1}B_{1}C_{1}D_{1}E_{1}F_{1} and A_{k}B_{k}C_{k}D_{k}E_{k}F_{k} with two additional vertices V_{1} and V_{k}. The vertices A_{1}, B_{1}, C_{1}, D_{1}, E_{1}, F_{1}, A_{k}, B_{k}, C_{k}, D_{k}, E_{k}, F_{k} are of order 5 and the others are of order 6.

Other polyhedra from the whole series can be obtained by GP algorithm by discarding vertices in the following order and adding new edges as it is indicated in parentheses (Fig. 3.): E_{k} (D_{k}F_{k−1}, D_{k}F_{k}), F_{k} (F_{k−1}V_{2}, F_{k−1}A_{k}), D_{k} (E_{k−1}V_{2}, E_{k−1}C_{k}), C_{k} (D_{k−1}V_{2}, D_{k−1}B_{k}), A_{k} (A_{k−1}V_{2}, A_{k−1}B_{k}), B_{k} (V_{2}B_{k−1}, V_{2}C_{k−1}). The last iteration gives a polyhedron from the basic series. The vertices of new polyhedra are of order 5 or 6 except the vertex F_{k−1} for n = 6k (i.e., the polyhedron obtained after discarding vertex F_{k}) which is of order 7.

4. The cone triangulation

A much better estimation of the minimal number of tetrahedra is obtained by the cone triangulation [10]. One of the vertices is the common apex, which builds one tetrahedron with each of (triangular) faces of the polyhedra, except with these containing it. By Euler’s theorem, a polyhedron with n vertices has 2n − 4 faces if all of them are triangular. So, the number of tetrahedra in triangulation is at most 2n − 10, since, for n ⩾ 12, each polyhedron has at least one vertex of order 6 or more. Sleator, Tarjan and Thurston in [10] considered some cases of “bad” polyhedra, which need a great number of tetrahedra for triangulation. It is proved, using hyperbolic geometry, that the minimal number of tetrahedra, necessary for triangulating such polyhedra, is close to 2n − 10. That value is tight for one series of polyhedra, which exists for a sufficiently great n. Computer investigation of the equivalent problem of rotatory distance confirms, for 12 ⩽ n ⩽ 18, that there exist polyhedra, with the smallest necessary number of tetrahedra equal to 2n−10. This was the reason why the authors gave a hypothesis that the same statement is true for any n ⩾ 12. To prove this hypothesis, it would be good to check when the cone triangulation of polyhedra gives the smallest number of tetrahedra and how it is possible to improve it in other cases. With this aim, the authors gave in [10] an example of polyhedron, which had vertices of great order and for which there existed a triangulation better than the cone one. They also gave an advice on how to improve the method in this and some similar cases. The polyhedra with vertices of great order give less than 2n − 10 tetrahedra in the cone triangulation anyway, so, it is better to consider vertices of small order—3 or 4 if given polyhedra contain them.

Theorem 4.1. Let V be one of the vertices of a polyhedron P whose order is maximal. If the polyhedron P has a vertex of order 3 different and not connected with V, or a sequence of at least 2 vertices of order 4 connected between themselves into a chain, each of them different and not connected with V, then the cone triangulation of P with apex V will not give the smallest number of tetrahedra.

Proof. It is useful to apply the iterations of GP algorithm to the polyhedron as long as it has vertices of order 3, because each iteration gives then only one tetrahedron. Cone triangulation gives the same effect only for vertices connected with apex V. Otherwise, the vertex of order 3, neighbour vertices and apex V build a triangular bipyramid, which, by cone triangulation, gives 3 tetrahedra.

Suppose that a polyhedron P with n vertices has a sequence of k < n−6 vertices A_{1}, A_{2}, …, A_{k} of order 4 connected by edges A_{i}A_{i+1} (i = 1, …, k−1), A_{j}T_{1}, A_{j}T_{2} (j = 1, …, k), A_{1}R, A_{k}S, RT_{1}, RT_{2}, ST_{1}, ST_{2}, where R and S are of order greater than 4. Similarly as for the bipyramid, the best way to triangulate the part of P containing vertices R, S, A_{1}, A_{2}, …, A_{k}, T_{1}, T_{2} is to use tetrahedra surrounding T_{1}T_{2}: RA_{1}T_{1}T_{2}, A_{i}A_{i+1}T_{1}T_{2} (i = 1, …, k − 1), and A_{k}ST_{1}T_{2}. Let us call a triangulation of P “bipyramidal” if it contains the mentioned tetrahedra, and the remaining part P^{∗} of polyhedron P (with faces RT_{1}T_{2} and ST_{1}T_{2}) is triangulated by cone triangulation with apex V. If the order of vertex V of polyhedron P is v, then the cone triangulation of P gives 2n − 4 − v tetrahedra and the bipyramidal one, when V differs from the vertices R, S, T_{1}, T_{2}, A_{j} (j = 1, …, k), gives [k + 1] + [2(n − k) − 4 − v] = 2n − 4 − v − k + 1 tetrahedra. Since k ⩾ 2, the bipyramidal triangulation gives a smaller number of tetrahedra. Even when V coincides with R or S, the bipyramidal triangulation gives good results for k ⩾ 3, since after discarding tetrahedra around T_{1}T_{2}, vertex V is of order v − 1, this triangulation gives 2n − 4 − v − k + 2 tetrahedra. If the part P^{∗} of polyhedron P has a vertex V_{1} of order greater than v − 1, it is also possible to divide P^{∗} by a better cone triangulation with apex V_{1} (with 2n − 4 − v − k + 1 tetrahedra).

Remarks. 1. Each of the vertices A_{j} (j = 1, …, k) is of order 4 and it is not suitable to use it as the apex of cone triangulation, since there are vertices of greater order.

2. If V coincides with T_{1} or T_{2}, the two mentioned triangulations are the same.

3. In order to triangulate a given polyhedron P, it is obviously good to apply the previous whenever there exists any vertex of order 3 and 4 and, if it is necessary, more times.

From everything mentioned before, it is clear that candidates for the minimal triangulation into a great number of tetrahedra (near or equal to 2n − 10) are polyhedra with all vertices of order 5 or 6. So, the following theorem is significant:

Theorem 4.2. For n ⩾ 14 there exists a polyhedron with n vertices which are either of order 5 or 6.

Proof. In the proof of Theorem 3.2.(2), the basic series was described for n = 6k + 2 (k ⩾ 2) which fulfilled the condition of the theorem. For other values

Fig. 4

of n, vertices will be added one by one. The first three vertices of order 5 can be added around vertex V_{1} in the following way (Fig. 4.): vertex P is connected with V_{1}, A_{1}, B_{1}, C_{1}, D_{1} (edges V_{1}B_{1} and V_{1}C_{1} vanish); vertex Q is connected with V_{1}, F_{1}, A_{1}, B_{1}, P (edges A_{1}V_{1} and A_{1}P vanish); vertex R is connected with V_{1}, P, C_{1}, D_{1}, E_{1} (edges D_{1}V_{1} and D_{1}P vanish). A similar procedure can be repeated around vertex V_{k}. Since all these polyhedra fulfill the condition of the theorem, the theorem is proved for all values of n.

Acknowledgement. I would like to thank DAAD (Germany) for the support and my geometrician colleagues at the University of Potsdam, headed by Prof. Benno Klotzek, for their hospitality and friendly support during my stay in Potsdam in October-November 1997, where I did a substantial part of this work.

REFERENCES

[1] Avis, D., ElGindy, H., Triangulating point sets in space, Discrete Comput. Geom., 2 (1987), 99–111.

[2] Chazelle, B., Triangulating a simple polygon in linear time, Discrete Comput. Geom., 6, 5, (1991), 485–524.

[3] Dirac, G. A., Stojaković, M. D., Problem četiri boje, Matematička biblioteka, Beograd, 1960 (in Serbian).

[4] Edelsbrunner, H., Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.

[5] Edelsbrunner, H., Preparata, F. P., West, D. B., Tetrahedrizing point sets in three dimensions, J. Simbolic Computation, 10, (1990), 335–347.

[6] Lee, C. W., Subdivisions and triangulations of polytopes, Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O’Rourke, eds., CRC Press LLC, Boca Raton, 1997, chapter 14, 271–290.

[7] Ruppert, J., Seidel, R., On the difficulty of triangulating threedimensional nonconvex polyhedra, Discrete Comput. Geom., 7, (1992), 227–253.

[8] Seidel, R., A simple and fast incremental randomized algorithm for triangulating polygons, Discrete Comput. Geom., 1, 1, (1991), 51–64.

[9] Schonhardt, E., Über die Zerlegung von Dreieckspolyedern in Tetraeder, Math. Ann., 98, (1928), 309–312.

[10] Sleator, D. D., Tarjan, R. E., Thurston, W. P., Rotatory distance, triangulations, and hyperbolic geometry, J. Amer. Math. Soc., 1, 3, (1988).

(received 29.06.2002, in revised form 26.11.2004)

Faculty of Organizational Sciences, Jove Ilica 154, YU-11000 Belgrade