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?
Minimum equidecomposable decomposition
ds.algorithms;computational geometry;polygon