Paper by Martin L. Demaine

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.

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 − ε.

This paper is also available from SpringerLink.

Currently unavailable. If you are in a rush for copies, contact me.
[Google Scholar search]

Related papers:
Dissection_JCDCGG2015 (k-piece dissection is NP-hard)

See also other papers by Martin Demaine.
These pages are generated automagically from a BibTeX file.
Last updated November 20, 2018 by Martin Demaine.