Paper by Erik D. Demaine

Reference:

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, and Anak Yodpinyanee, “Dissection with the Fewest Pieces is Hard, Even to Approximate”, in Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, volume 9943, Kyoto, Japan, September 14–16, 2015, pages 37–48.

Abstract:

We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of 1 + 1/1080 − ε.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (367k).

See information on file formats.

[Google Scholar search]

Related papers:

Dissection_JCDCGG2015 (k-piece dissection is NP-hard)