MATEMATIČKI VESNIK
МАТЕМАТИЧКИ ВЕСНИК



MATEMATIČKI VESNIK
Algorithms for triangulating polyhedra into a small number of tethraedra
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.

Creative Commons License

Keywords: Triangulation of polyhedra, minimal triangulation.

MSC: 52C17, 52B05, 05B40

Pages:  1--9     

Volume  57 ,  Issue  1$-$2 ,  2005