tailieunhanh - Convex polyhedra with triangular faces and cone triangulation

Considering the problem of the minimal triangulation for a given polyhedra (dividing polyhedra into tetrahedra) it is known that the cone triangulation provides the number of tetrahedra which is the smallest, or the closest to it. It is also shown that when we want to know whether the cone triangulation is the minimal one, it is necessary to find the order of all vertices, as well as the order of “separating circles”. | Yugoslav Journal of Operations Research 21 (2011), Number 1, 79-92 DOI: CONVEX POLYHEDRA WITH TRIANGULAR FACES AND CONE TRIANGULATION Milica STOJANOVIĆ Faculty of Organizational Sciences, Belgrade, Serbia milicas@ Milica VUČKOVIĆ Faculty of Organizational Sciences, Belgrade,Serbia milica@ Received: December 2010 / Accepted: May 2011 Abstract: Considering the problem of the minimal triangulation for a given polyhedra (dividing polyhedra into tetrahedra) it is known that the cone triangulation provides the number of tetrahedra which is the smallest, or the closest to it. It is also shown that when we want to know whether the cone triangulation is the minimal one, it is necessary to find the order of all vertices, as well as the order of “separating circles”. Here, we will give algorithms for testing the necessary condition for the cone triangulation if it is the minimal one. The algorithm for forming the cone triangulation will also be given. Keywords: Triangulation of polyhedra, minimal triangulation, graph algorithms, abstract data type of graph. MSC: Primary: 52C17, 68R10; Secondary: 52B05, 05C85, 68P05, 68Q65 1. INTRODUCTION The division of any polygon with n-3 diagonals into n-2 triangles without gaps and overleaps is known. Such a division is called triangulation. The generalization of this process to higher dimensions is also called triangulation. It divides a polyhedron (polytope) into tetrahedra (simplices). The problem of triangulation in higher dimensions is much more complicated. It is impossible to triangulate some nonconvex polyhedra [9] in three-dimensional space, and it is also proved that triangulations of the same polyhedron may lead to different numbers of tetrahedra [7], [10]. Considering the smallest and the largest number of tetrahedra in 80 , /Convex polyhedra with triangular faces triangulation (the minimal and the maximal triangulation, respectively), the .