Dissection with the Fewest Pieces is Hard, Even to Approximate

Dissection with the Fewest Pieces is Hard, Even to Approximate

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

Bibliographic Details
Main Authors:	Manurangsi, Pasin, Bosboom, Jeffrey William, Demaine, Erik D, Demaine, Martin L, Lynch, Jayson R., Rudoy, Mikhail, Yodpinyanee, Anak
Other Authors:	Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format:	Article
Language:	en_US
Published:	Springer International Publishing 2018
Online Access:	http://hdl.handle.net/1721.1/114897 https://orcid.org/0000-0002-8526-4085 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-3466-6543

Internet

http://hdl.handle.net/1721.1/114897
https://orcid.org/0000-0002-8526-4085
https://orcid.org/0000-0003-3803-5703
https://orcid.org/0000-0002-3466-6543