Minimale gleich zusammensetzbare Zersetzung

Wenn zwei Polyeder und , sind und gleich zusammensetzbar, wenn es endliche Mengen von Polyedern und so dass und für alle , kongruent sind und . Es ist bekannt, dass, wenn und Polygone gleicher Fläche sind, eine solche Gleichkomposition immer existiert und dass dies im Allgemeinen nicht für höhere Dimensionen gilt . $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$

Ich bin gespannt auf die Komplexität des Problems der minimalen Equidecomposition:

Finden Sie für zwei Polygone und eine Gleichkomposition und , die minimiert .$P$$Q$$P_1, \ldots, P_n$$Q_1, \ldots, Q_n$$n$

Gibt es dafür Algorithmen (genau, polynomisch, exponentiell, approximierend)? Ist die Komplexität bekannt?

Für getrennte eindimensionale Bereiche mit ganzzahligen Koordinaten ist die Gleichkomposition in eine minimale Anzahl von Teilen durch eine einfache Reduktion auf 3SUM stark NP-hart: Wenn eine Form Segmente hat, deren Längen die 3SUM-Eingänge sind, und die andere Segmente, deren Längen die Bins sind Sie müssen sie einpacken, dann können Sie dies ohne zusätzliches Schneiden tun, wenn die 3SUM-Instanz lösbar ist. Für zweidimensionale Polygone bleibt es selbst für verbundene Bereiche schwierig: Verdicken Sie die Segmente eines eindimensionalen Problems zu Rechtecken mit Einheitshöhe und verbinden Sie sie durch dünne "Strings", die eine zu kleine Fläche haben, um den 3SUM-Teil des Problems zu beeinflussen sind aber bei der Zersetzung leicht zu handhaben.

(Haftungsausschluss: Ich habe diese Reduktionsidee aus einer noch nicht veröffentlichten gemeinsamen Arbeit mit vielen anderen Personen über die Härte einiger anderer Probleme entlehnt.)