Triangulating a non-convex polytype

ABSTRACT

This paper is concerned with the problem of partitioning a three-dimensional polytope into a small number of elementary convex parts. The need for such decompositions arises in tool design, computer-aided manufacturing, finite-element methods, and robotics. Our main result is an algorithm for decomposing a polytope with n vertices and r reflex edges into &Ogr;(n+r2) tetrahedra. This bound is asymptotically tight in the worst case. The algorithm is simple and practical. Its running time is &Ogr;(nr + r2 log r).

REFERENCES

• 1: B. Aronov , M. Sharir, Triangles in space or building (and analyzing) castles in the Air, Proceedings of the fourth annual symposium on Computational geometry, p.381-391, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73432]
• 2: Baker, T.J. Three-dimensional mesh generation by triangulation of arbitrary point sets, Dept. Mechanical Engineering, Princeton Univ. 1986.
• 3: Brenda S. Baker , Eric Grosse , Conor S. Rafferty, Nonobtuse triangulation of polygons, Discrete & Computational Geometry, v.3 n.2, p.147-168, Jan, 1988 [doi>10.1007/BF02187904]
• 4: Baumgart, B.G. A polyhedron representation for cornputer vision, 1975 National Computer Conference, AFIPS Conf. Proceedings, 44, AFIPS Press (1975), 589-596.
• 5: Canny, J.F. A new algebraic method for motion planning and real geometry, Proc. 28th Annu. IEEE Symp. on Foundat. of Computer Science (1987), 39-48.
• 6: Bernard Chazelle, Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm, SIAM Journal on Computing, v.13 n.3, p.488-507, August 1984 [doi>10.1137/0213031]
• 7: ChazeIIe, B. Approzimation and decomposition of shapes, Advances in Robotics, Vol.1: Algorithmic and Geometric Aspects of Robotics, (J.T. Schwartz and C.K. Yap, ed.), Lawrence Erlbaum Associates (1987), 145-185.
• 8: Chazalle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M. Point location in real-algebraic varieties and its applications, ICALP, 1989.
• 9: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 10: D. P. Dobkin , M. J. Laszlo, Primitives for the manipulation of three-dimensional subdivisions, Proceedings of the third annual symposium on Computational geometry, p.86-99, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41967]
• 11: H Edelsbrunner , J O'Rouke , R Seiel, Constructing arrangements of lines and hyperplanes with applications, SIAM Journal on Computing, v.15 n.2, p.341-363, May 1986 [doi>10.1137/0215024]
• 12: Feng, H., PavIidis, T. Decomposition polygons into simpler components: Feature generation for syntactic pattern recognition, IEEE Trans. Comp., C-24 (1975), 636-650.
• 13: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 14: Andrzej Lingas, The Power of Non-Rectilinear Holes, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.369-383, July 12-16, 1982
• 15: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 16: MuIIer D.E., Preparata, F.P. Finding the intersection of two convex polyhedra, Theoret. Comput. Sci. 7 (1978), 217-236.
• 17: Joseph O'Rourke, Art gallery theorems and algorithms, Oxford University Press, Inc., New York, NY, 1987
• 18: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 19: David Prill, On approximations and incidence in cylindrical algebraic decompositions, SIAM Journal on Computing, v.15 n.4, p.972-993, Nov. 1986 [doi>10.1137/0215069]
• 20: Schachter, B. Decomposition of polygons into convex sets, IEEE Trans. Camp., C-27 (1978), 1078-1082.
• 21: Schwartz, J.T., Sharir, M. On the "piano movers" problem. II: General techniques for computing topological properties of real algebraic manifolds, Adv. in Appl. Math. 4 (1983), 298-351.
• 22: Warren Douglas Smith, Studies in computational geometry motivated by mesh generation, 1989
• 23: Whitney, H. Elementary structure of real algebraic varieties, Annals of Math. 66 (1957).

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided manufacturing (CAM)

General Terms:
Algorithms, Theory