Dissection with the Fewest Pieces is Hard, Even to Approximate

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-\epsilon$.

18 pages, 9 figures