Dissection with the Fewest Pieces is Hard, Even to Approximate

Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy, Anak Yodpinyanee

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-\varepsilon $$ .
BibTeX
@inproceedings{bosboom2015dissection,
  author = {Jeffrey Bosboom and Erik D. Demaine and Martin L. Demaine and Jayson Lynch and Pasin Manurangsi and Mikhail Rudoy and Anak Yodpinyanee},
  title = {{Dissection with the Fewest Pieces is Hard, Even to Approximate}},
  booktitle = {JCDCGG},
  year = {2015},
  url = {https://openreview.net/forum?id=HhjhG27sok5},
}
Figure