Convex polyhedra with triangular faces and cone triangulation

Authors

  • Milica Stojanović Faculty of Organizational Sciences, Belgrade
  • Milica Vučković Faculty of Organizational Sciences, Belgrade

DOI:

https://doi.org/10.2298/YJOR1101079S

Keywords:

Triangulation of polyhedra, minimal triangulation, graph algorithms, abstract data type of graph

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.

References

Baumgart, B.G. (1975) A polyhedron representation for computer vision. u: Proceedings of the 1975 National Computer Conference. AFIPS Conference Proceedings, Reston, Va: AFIPS Press, vol. 44

Below, A., Loera, J.A., Gebert, J.R. (2000) The complexity of finding small triangulations of convex 3-polytopes. arXiv, math 0012177v1

Brinkmann, G., McKay, B.D. (2007) Fast generation of planar graphs. Communications in Mathematical and in Computer Chemistry / MATCH, vol. 58, br. 2, str. 323-357

Chin, F.Y.L., Fung, S.P.Y., Wang, C.A. (2001) Approximation for minimum triangulations of simplicial convex 3-polytopes. Discrete Computational Geometry, 26, br. 4, 499-511

Develin, M. (2004) Mаximal triangulations of a regular prism. J Combin. Theory Ser. A, Ser. A, 106, br. 1, 159-164

Edelsbrunner, H., Preparata, F.P., West, D.B. (1990) Tetrahedrizing point sets in three dimensions. Journal of Symbolic Computation, 10, 4, 335-347

Goodrich, M., Tamassia, R. (2001) Data structures and algorithms in Java. John Wiley & Sons

Mccormell, J. (2001) Analysis of algorithms: An active learning approach. Jones and Bartlett Publishers

Ruppert, J., Seidel, R. (1992) On the difficulty of triangulating three-dimensional nonconvex polyhedra. Discrete and Computational Geometry, 7, 3, 227-253

Sleator, D.D., Tarjan, R.E., Thurston, W.P. (1988) Rotation distance, triangulations, and hyperbolic geometry. J Am Math Soc, 1, 3, 647-681

Stojanović, M. (2008) Triangulations of some cases of polyhedra with a small number of tetrahedra. Kragujevac Journal of Mathematics, br. 31, str. 85-93

Stojanović, M., Vučković, M. (2007) Algorithms for investigating optimality of cone triangulation for a polyhedron. Kragujevac Journal of Mathematics, br. 30, str. 327-342

Stojanović, M.A. (2005) Algorithms for triangulating polyhedra into a small number of tetrahedra. Matematički vesnik, vol. 57, br. 1-2, str. 1-9

Downloads

Published

2011-03-01

Issue

Vol. 21 No. 1 (2011)

Section

Research Articles

License

Copyright (c) YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.