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., “A polyhedron representation for computer vision,” in: Proceedings of the 1975 National Computer Conference, AFIPS Conference Proceedings, vol. 44. AFIPS Press, Reston, Va., 1975.

Below, A., Loera, J.A., and Gebert, J.R., “The complexity of finding small triangulations of convex 3-polytopes,” arXiv:math/0012177v1.

Brinkmann, G., and McKay, B.D., “Fast generation of planar graphs,” MATCH Commun. Math. Comput. Chem., 58 (2) (2007) 323-357.

Goodrich M., and Tamassia R., Data Structures and Algorithms in Java, Second Edition. John Wiley & Sons, 2001.

Chin, F.Y.L., Fung, S.P.Y., and Wang, C.A., “Approximation for minimum triangulations of simplicial convex 3-polytopes,” Discrete Comput. Geom., 26 (4) (2001) 499-511.

Develin, Mike, “Maximal triangulations of a regular prism,” J. Comb. Theory, Ser.A, 106 (1) (2004) 159-164.

Edelsbrunner, H., Preparata, F.P., and West, D.B., “Tetrahedrizing point sets in three dimensions,” J. Symbolic Computation, 10 (1990) 335-347.

McConnell J., Analysis of Algorithms: An Active Learning Approach, Jones and Bartlett Publishers, 2001.

Ruppert, J., and Seidel, R., “On the difficulty of triangulating three-dimensional nonconvex polyhedra,” Discrete Comput. Geom., 7 (1992) 227-253.

Sleator, D.D., Tarjan, R.E., and Thurston, W.P., “Rotatory distance, triangulations, and hyperbolic geometry,” J. of the Am. Math. Soc., 1 (3) (1988).

Stojanović, M., “Algorithms for triangulating polyhedra with a small number of tetrahedra,” Mat. Vesnik, 57 (2005) 1-9.

Stojanović, M., “Triangulations of some cases of polyhedra with a small number of tetrahedra,” Krag. J. Math., 31 (2008) 85-93.

Stojanović, M., and Vučković, M., “Algorithms for investigating optimality of cone triangulation for a polyhedron,” Krag. J. Math., 30 (2007) 327-342.

Downloads

Published

2011-03-01

Issue

Vol. 21 No. 1 (2011)

Section

Research Articles

License

Copyright (c) 2011 YUJOR

Creative Commons License

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