Descomposición mínima equidecomposible

Dados dos poliedros y Q , P y Q son equícompuestos si hay conjuntos finitos de poliedros P 1 , ... , P n y Q 1 , ... , Q n de manera que P i y Q i son congruentes para todo i , P = ∪ n i = 1 P i y Q = ∪ n i = 1$P$$Q$$P$$Q$$P_1, \ldots, P_n$$Q_1, \ldots, Q_n$$P_i$$Q_i$$i$$P = \cup_{i=1}^n P_i$ . Se sabeque si P y Q son polígonos de igual área,siempre existeunaequidecomposicióny estono se cumple en general para dimensiones superiores. $Q = \cup_{i=1}^n Q_i$$P$$Q$

Tengo curiosidad acerca de la complejidad del problema de equidecomposición mínima:

Para dos polígonos y Q , encuentre una equidecomposición P 1 , ... , P n y Q 1 , ... , Q n que minimice n .$P$$Q$$P_1, \ldots, P_n$$Q_1, \ldots, Q_n$$n$

¿Existen algoritmos (exactos, polinómicos, exponenciales, de aproximación) para esto? ¿Se conoce la complejidad?

Para regiones unidimensionales desconectadas con coordenadas enteras, la composición equidistante en un número mínimo de piezas es fuertemente NP-dura mediante una reducción fácil a 3SUM: si una forma tiene segmentos cuyas longitudes son las entradas 3SUM y la otra tiene segmentos cuyas longitudes son los contenedores debe empacarlos, luego puede hacerlo sin cortes adicionales si la instancia de 3SUM es solucionable. Para los polígonos bidimensionales sigue siendo difícil, incluso para las regiones conectadas: engrosar los segmentos de un problema unidimensional a rectángulos de altura unitaria y conectarlos mediante "cadenas" delgadas que tienen un área demasiado pequeña para afectar la parte 3SUM del problema pero son fáciles de manejar en la descomposición.

(Descargo de responsabilidad: tomé prestada esta idea de reducción de un trabajo conjunto aún no publicado con muchas otras personas sobre la dureza de algunos otros problemas).