@inproceedings{25baaa6f8269470da1be70914b723cb3,

title = "Triangulating a nonconvex polytope",

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, 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).",

author = "Bernard Chazelle and Leonidas Palios",

note = "Funding Information: This research was supported in part Science Foundation under Grant CCR- Publisher Copyright: {\textcopyright} 1989 ACM.; 5th Annual Symposium on Computational Geometry, SCG 1989 ; Conference date: 05-06-1989 Through 07-06-1989",

year = "1989",

month = jun,

day = "5",

doi = "10.1145/73833.73875",

language = "English (US)",

series = "Proceedings of the Annual Symposium on Computational Geometry",

publisher = "Association for Computing Machinery",

pages = "393--400",

booktitle = "Proceedings of the 5th Annual Symposium on Computational Geometry, SCG 1989",

}