Dekomposisi minimum yang dapat digabungkan secara merata

Diberikan dua polyhedra dan Q , P dan Q sama-sama dapat dikomposisikan jika ada set polyhedra P 1 yang terbatas , ... , P n dan Q 1 , ... , Q n sedemikian rupa sehingga P i dan Q i kongruen untuk semua i , P = ∪ n i = 1 P i dan 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$ . Diketahuibahwa jika P dan Q adalah poligon dengan luas yang sama,komposisi yang samaselalu ada dan bahwa initidak berlaku secara umum untuk dimensi yang lebih tinggi. $Q = \cup_{i=1}^n Q_i$$P$$Q$

Saya ingin tahu tentang kerumitan masalah komposisi kesetaraan minimum:

Untuk dua poligon dan Q , temukan persamaan posisi P 1 , ... , P n dan Q 1 , ... , Q n yang meminimalkan n .$P$$Q$$P_1, \ldots, P_n$$Q_1, \ldots, Q_n$$n$

Apakah ada algoritma (tepat, polinomial, eksponensial, perkiraan) untuk ini? Apakah kerumitannya diketahui?

Untuk daerah satu dimensi yang terputus dengan koordinat bilangan bulat, komposisi ekuivalen ke dalam jumlah minimum kepingan sangat kuat NP-hard melalui pengurangan mudah menjadi 3SUM: jika satu bentuk memiliki segmen yang panjangnya adalah input 3SUM dan yang lain memiliki segmen yang panjangnya adalah tempat sampah Anda harus mengemasnya, maka Anda dapat melakukannya tanpa memotong tambahan jika instance 3SUM dapat dipecahkan. Untuk poligon dua dimensi tetap sulit, bahkan untuk daerah yang terhubung: kentalkan segmen masalah satu dimensi menjadi satuan tinggi persegi panjang dan hubungkan dengan "string" tipis yang memiliki area terlalu kecil untuk memengaruhi bagian 3SUM dari masalah tetapi mudah ditangani dalam dekomposisi.

(Penafian: Saya meminjam ide pengurangan ini dari beberapa kerja bersama yang belum dipublikasikan dengan banyak orang lain mengenai kekerasan dari beberapa masalah lain.)