Dissection with the Fewest Pieces is Hard, Even to Approximate

Autor:	Martin L. Demaine, Jeffrey Bosboom, Erik D. Demaine, Anak Yodpinyanee, Jayson Lynch, Pasin Manurangsi, Mikhail Rudoy
Rok vydání:	2016
Předmět:	Combinatorics 010201 computation theory & mathematics Simple (abstract algebra) 010102 general mathematics Polygon medicine 0102 computer and information sciences Dissection (medical) 0101 mathematics medicine.disease 01 natural sciences Mathematics
Zdroj:	Lecture Notes in Computer Science ISBN: 9783319485317 JCDCGG
DOI:	10.1007/978-3-319-48532-4_4
Popis:	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 \).
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::6a9b510fcc5f3d33ae9f2ce50bff3c10 https://doi.org/10.1007/978-3-319-48532-4_4 Zobrazit plný text záznamu