Optimal Convex Decompositions

Research output: Chapter in Book/Report/Conference proceedingChapter

71 Scopus citations

Abstract

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
Pages63-133
Number of pages71
EditionC
DOIs
StatePublished - Jan 1 1985

Publication series

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

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

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

  • Cite this

    Chazelle, B., & Dobkin, D. P. (1985). Optimal Convex Decompositions. In Machine Intelligence and Pattern Recognition (C ed., pp. 63-133). (Machine Intelligence and Pattern Recognition; Vol. 2, No. C). https://doi.org/10.1016/B978-0-444-87806-9.50009-8