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

V.J. Dielissen, A. Kaldewaij

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

19 Citaten (Scopus)
4 Downloads (Pure)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)1-6
TijdschriftInformation Processing Letters
Volume38
Nummer van het tijdschrift1
DOI's
StatusGepubliceerd - 1991

Vingerafdruk

Duik in de onderzoeksthema's van 'Rectangular partition is polynomial in two dimensions but NP-complete in three'. Samen vormen ze een unieke vingerafdruk.

Citeer dit