@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 = "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",
}