Minimalny rozkład równomierny

Biorąc pod uwagę, że dwa wielościany i , i są jeśli istnieją skończone zestawy wielościanów i takie, że i są zgodne dla wszystkich , i . Wiadomo, że jeżeli i są wielokąty o jednakowej powierzchni, takie equidecomposition zawsze występuje i że nie posiada w ogólności dla większych wymiarów . Q P Q P 1 , … , P n Q 1 , … , Q n P i Q i i P = ∪ n i = 1 P i Q = ∪ n i = 1 Q i P $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$

Jestem ciekawy co do złożoności problemu minimalnego równowaenia:

Dla dwóch wielokątów i znajdź i która minimalizuje .Q P 1 , … , P n Q 1 , … , Q n$P$$Q$$P_1, \ldots, P_n$$Q_1, \ldots, Q_n$$n$

Czy istnieją do tego algorytmy (dokładne, wielomianowe, wykładnicze, aproksymacyjne)? Czy złożoność jest znana?

W przypadku rozłączonych jednowymiarowych obszarów o współrzędnych całkowitych równomierny rozkład na minimalną liczbę elementów jest silnie NP-trudny dzięki łatwemu zmniejszeniu do 3SUM: jeśli jeden kształt ma segmenty, których długości są wejściami 3SUM, a drugi ma segmenty, których długości są przedziałami musisz je spakować, a następnie możesz to zrobić bez dodatkowego cięcia, jeśli instancja 3SUM jest rozwiązalna. W przypadku dwuwymiarowych wielokątów jest to trudne nawet dla połączonych obszarów: zgrub segmenty jednowymiarowego problemu do prostokątów o wysokości jednostkowej i połącz je cienkimi „łańcuchami”, które mają zbyt mały obszar, aby wpłynąć na część problemu 3SUM ale są łatwe w obsłudze podczas rozkładu.

(Zastrzeżenie: pożyczyłem ten pomysł na redukcję od pewnej jeszcze nieopublikowanej wspólnej pracy z wieloma innymi ludźmi na temat twardości innych problemów).