Optimal Convex Decompositions

Bernard Chazelle, David Paul Dobkin

Research output: Chapter in Book/Report/Conference proceedingChapter

90 Scopus citations


The problem of decomposing a non-convex simple polygon into a minimum number of convex polygons is solved. The decomposition allows for the introduction of Steiner points. Two algorithms are proposed. The first verifies that the problem is doable in polynomial time. The second provides an efficient method. Along the way, numerous results of independent interest in pure geometry as well as geometric complexity are stated.

Original languageEnglish (US)
Title of host publicationMachine Intelligence and Pattern Recognition
Number of pages71
StatePublished - Jan 1 1985

Publication series

NameMachine Intelligence and Pattern Recognition
ISSN (Print)0923-0459

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Optimal Convex Decompositions'. Together they form a unique fingerprint.

Cite this