Minimum equidecomposable decomposition

Question

Given two polyhedra $P$ and $Q$, $P$ and $Q$ are are equidecomposable if there are finite sets of polyhedra $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ such that $P_i$ and $Q_i$ are congruent for all $i$, $P = \cup_{i=1}^n P_i$ and $Q = \cup_{i=1}^n Q_i$. It is known that if $P$ and $Q$ are polygons of equal area, such an equidecomposition always exists and that this does not hold in general for higher dimensions.

I am curious as to the complexity of the minimum equidecomposition problem:

For two polygons $P$ and $Q$, find a equidecomposition $P_1, \ldots, P_n$ and $Q_1, \ldots, Q_n$ that minimizes $n$.

Are there algorithms (exact, polynomial, exponential, approximation) for this? Is the complexity known?

Answer 1

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.)