Dissection with the Fewest Pieces is Hard, Even to Approximate
Lists
Only you see this
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},
}