Minimum equidecomposable decomposition
For disconnected one-dimensional regions with integer coordinates, equidecomposition into a minimum number of pieces is strongly NP-hard via an easy reduction to 3SUM: if one shape has segments whose lengths are the 3SUM inputs and the other has segments whose lengths are the bins you have to pack them in, then you can do it with no additional cutting iff the 3SUM instance is solvable. For two-dimensional polygons it remains hard, even for connected regions: thicken the segments of a one-dimensional problem to unit-height rectangles and connect them by thin "strings" that have too small an area to affect the 3SUM part of the problem but are easy to handle in the decomposition.

(Disclaimer: I borrowed this reduction idea from some not-yet-published joint work with many other people on hardness of some other problems.)