Dissection with the Fewest Pieces is Hard, Even to Approximate

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

arxiv: 1512.06706 · v1 · pith:IRQCS7KZnew · submitted 2015-12-21 · 💻 cs.CG

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 This is my paper

classification 💻 cs.CG

keywords piecesfewestanotherapproximateapproximatingdissectdissectioneven

0 comments

read the original 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$.

This paper has not been read by Pith yet.

Dissection with the Fewest Pieces is Hard, Even to Approximate

discussion (0)