Decomposing the boundary of a nonconvex polyhedron

Bernard Chazelle, Leonidas Palios

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

7 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsOtto Nurmi, Esko Ukkonen
PublisherSpringer Verlag
Pages364-375
Number of pages12
ISBN (Print)9783540557067
DOIs
StatePublished - Jan 1 1992
Event3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992 - Helsinki, Finland
Duration: Jul 8 1992Jul 10 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume621 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Scandinavian Workshop on Algorithm Theory, SWAT 1992
CountryFinland
CityHelsinki
Period7/8/927/10/92

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Decomposing the boundary of a nonconvex polyhedron'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., & Palios, L. (1992). Decomposing the boundary of a nonconvex polyhedron. In O. Nurmi, & E. Ukkonen (Eds.), Algorithm Theory – SWAT 1992 - 3rd Scandinavian Workshop on Algorithm Theory, Proceedings (pp. 364-375). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 621 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-55706-7_33