Decomposing a polygon into its convex parts

Bernard Chazelle, David Dobkin

Research output: Contribution to journalConference articlepeer-review

77 Scopus citations


A common operation in geometric computing is the decomposition of complex structures into more basic structures. Since it is easier to apply most algorithms to triangles or arbitrary convex polygons, there is considerable interest in finding fast algorithms! for such decompositions. We consider the problem of decomposing a simple (non-convex) polygon into the union of a minimal number of convex polygons. Although the structure of the problem led to the conjecture that it was NP-complete, we have been able to reach polynomial time bounded algorithms for exact solution as well as low degree polynomial time bounded algorithm/or approximation methods.

Original languageEnglish (US)
Pages (from-to)38-48
Number of pages11
JournalProceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Apr 30 1979
Event11th Annual ACM Symposium on Theory of Computing, STOC 1979 - Atlanta, United States
Duration: Apr 30 1979May 2 1979

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Decomposing a polygon into its convex parts'. Together they form a unique fingerprint.

Cite this