Rectangular partition is polynomial in two dimensions but NP-complete in three

V.J. Dielissen, A. Kaldewaij

Research output: Contribution to journalArticleAcademicpeer-review

19 Citations (Scopus)
4 Downloads (Pure)

Abstract

The inherent computational complexity of polygon decomposition problems is of importance in the field of computational geometry. For one of these problems it is shown that the three-dimensional version is NP-complete whereas its two-dimensional version is polynomial. This provides an example for the conjecture posed by O'Rourke and Supowit.
Original languageEnglish
Pages (from-to)1-6
JournalInformation Processing Letters
Volume38
Issue number1
DOIs
Publication statusPublished - 1991

Fingerprint Dive into the research topics of 'Rectangular partition is polynomial in two dimensions but NP-complete in three'. Together they form a unique fingerprint.

  • Cite this