Decomposing the Boundary of a Nonconvex Polyhedron

B. Chazelle, L. Palios

Research output: Contribution to journalArticle

19 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 in r, 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 log r) time.

Original languageEnglish (US)
Pages (from-to)245-265
Number of pages21
JournalAlgorithmica (New York)
Volume17
Issue number3
DOIs
StatePublished - Mar 1997

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Decomposing the Boundary of a Nonconvex Polyhedron'. Together they form a unique fingerprint.

  • Cite this