Triangulating a nonconvex polytope

Bernard Chazelle, Leonidas Palios

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


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, finiteelement methods, and robotics. Our main result is an algorithm for decomposing a polytope with n vertices and t reflex edges into O(n+r2) tetrahedra. This bound is asymp totically tight in the worst case. The algorithm is simple and practical. Its running time is O(nr + r2 log r).

Original languageEnglish (US)
Title of host publicationProceedings of the 5th Annual Symposium on Computational Geometry, SCG 1989
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Electronic)0897913183
StatePublished - Jun 5 1989
Externally publishedYes
Event5th Annual Symposium on Computational Geometry, SCG 1989 - Saarbruchen, Germany
Duration: Jun 5 1989Jun 7 1989

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
VolumePart F130124


Other5th Annual Symposium on Computational Geometry, SCG 1989

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Triangulating a nonconvex polytope'. Together they form a unique fingerprint.

Cite this