@inproceedings{e8e2da0df5084fe492d9ee2c657b8969,

title = "Decomposing the boundary of a nonconvex polyhedron",

abstract = "We show that the boundary of a three-dimensional polyhedron with r reflex angles and arbitrary genus can be subdivided into O(r) connected pieces, each of which lies on the boundary of its convex hull. A remarkable feature of this result is that the number of these convex-like pieces is independent of the number of vertices. Furthermore, it is linear inr, which contrasts with a quadratic worst-case lower bound in the number of convex pieces needed to decompose the polyhedron itself. The number of new vertices introduced in the process is O(n). The decomposition can be computed in O(n + r logr) time.",

author = "Bernard Chazelle and Leonidas Palios",

year = "1992",

month = jan,

day = "1",

doi = "10.1007/3-540-55706-7_33",

language = "English (US)",

isbn = "9783540557067",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "364--375",

editor = "Otto Nurmi and Esko Ukkonen",

booktitle = "Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings",

address = "Germany",

note = "3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 ; Conference date: 08-07-1992 Through 10-07-1992",

}