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.
|Journal||Information Processing Letters|
|Publication status||Published - 1991|