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

V.J. Dielissen; A. Kaldewaij

doi:10.1016/0020-0190(91)90207-X

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

V.J. Dielissen, A. Kaldewaij

Mathematics and Computer Science

Research output: Contribution to journal › Article › Academic › peer-review

20 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 language	English
Pages (from-to)	1-6
Journal	Information Processing Letters
Volume	38
Issue number	1
DOIs	https://doi.org/10.1016/0020-0190(91)90207-X
Publication status	Published - 1991

Access to Document

10.1016/0020-0190(91)90207-X

Cite this

@article{672edc8d691b434587b7a42d9e05d3c7,

title = "Rectangular partition is polynomial in two dimensions but NP-complete in three",

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.",

author = "V.J. Dielissen and A. Kaldewaij",

year = "1991",

doi = "10.1016/0020-0190(91)90207-X",

language = "English",

volume = "38",

pages = "1--6",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

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

AU - Dielissen, V.J.

AU - Kaldewaij, A.

PY - 1991

Y1 - 1991

N2 - 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.

AB - 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.

U2 - 10.1016/0020-0190(91)90207-X

DO - 10.1016/0020-0190(91)90207-X

M3 - Article

SN - 0020-0190

VL - 38

SP - 1

EP - 6

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

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

Abstract

Access to Document

Fingerprint

Cite this