CONVEX PARTITIONS OF POLYHEDRA: A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM.

Research output: Contribution to journalArticle

152 Scopus citations

Abstract

The problem of partitioning a polyhedron into a minimum number of convex pieces is known to be NP-hard. The author establishes here a quadratic lower bound on the complexity of this problem, and he describes an algorithm that produces a number of convex parts within a constant factor of optimal in the worst case. The algorithm is linear in the size of the polyhedron and cubic in the number of reflex angles. Since in most applications areas, the former quantity greatly exceeds the latter, the algorithm is viable in practice.

Original languageEnglish (US)
Pages (from-to)488-507
Number of pages20
JournalSIAM Journal on Computing
Volume13
Issue number3
DOIs
StatePublished - 1984

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'CONVEX PARTITIONS OF POLYHEDRA: A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM.'. Together they form a unique fingerprint.

  • Cite this