# Minimum equidecomposable decomposition

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?

• welcome, great blog! – vzn Jul 2 '14 at 1:38