Paper by Erik D. 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.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 18, 2021 by