Decomposição equidecomponível mínima

Dado que dois poliedros e Q , P e Q são equidecomponíveis se houver conjuntos finitos de poliedros P_1, \ ldots, P_n e Q_1, \ ldots, Q_n de modo que P_i e Q_i sejam congruentes para todos i , P = \ cup_ {i = 1} ^ n P_i e Q = \ cup_ {i = 1} ^ n Q_i . Sabe-se que, se P e Q são polígonos de área igual, sempre existe uma composição equânime e que isso geralmente não se aplica a dimensões mais elevadas . $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$$Q = \cup_{i=1}^n Q_i$$P$$Q$

Estou curioso quanto à complexidade do problema de equidecomposition mínimo:

Para dois polígonos $P$ e $Q$ , encontre uma composição equivalente P_1, \ ldots, P_n$P_1, \ldots, P_n$ e $Q_1, \ldots, Q_n$ que minimize $n$ .

Existem algoritmos (exatos, polinomiais, exponenciais, aproximações) para isso? A complexidade é conhecida?

Para regiões unidimensionais desconectadas com coordenadas inteiras, a composição equitativa em um número mínimo de peças é fortemente NP-difícil através de uma fácil redução para 3SUM: se uma forma possui segmentos cujos comprimentos são as entradas 3SUM e a outra possui segmentos cujos comprimentos são os compartimentos você precisa empacotá-los e pode fazê-lo sem cortes adicionais, se a instância 3SUM for solucionável. Para polígonos bidimensionais, permanece difícil, mesmo para regiões conectadas: engrosse os segmentos de um problema unidimensional em retângulos de altura da unidade e conecte-os por "cordas" finas que possuem uma área muito pequena para afetar a parte 3SUM do problema mas são fáceis de manusear na decomposição.

(Isenção de responsabilidade: peguei emprestada essa ideia de redução de algum trabalho conjunto ainda não publicado com muitas outras pessoas sobre a dureza de outros problemas.)