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

Bibliographische Detailangaben
Hauptverfasser: Manurangsi, Pasin, Bosboom, Jeffrey William, Demaine, Erik D, Demaine, Martin L, Lynch, Jayson R., Rudoy, Mikhail, Yodpinyanee, Anak
Weitere Verfasser: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Artikel
Sprache:en_US
Veröffentlicht: Springer International Publishing 2018
Online Zugang: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

Online

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

Ähnliche Einträge