74 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

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Computer Vision and Pattern Recognition

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

Cite this