Минимальное равноразложимое разложение

10

Учитывая два многогранник и Q , P и Q является равносоставлены , если существует конечные множества многогранников P 1 , ... , P п и Q 1 , ... , Q п таких , что P я и Q я конгруэнтен для всех I , P = п я = 1 Р я и Q = п я = 1 QPQPQP1,,PnQ1,,QnPiQiiP=i=1nPi . Известночто если Р и Q являются многоугольники равной площади, такойequidecompositionвсегда существует и что этоне имеет места в целом для более высоких измерений. Q=i=1nQiPQ

Мне любопытно, что касается сложности проблемы минимального равного состава:

Для двух многоугольников и Q найдите эквивалентную композицию P 1 , , P n и Q 1 , , Q n, которая минимизирует n .PQP1,,PnQ1,,Qnn

Существуют ли алгоритмы (точные, полиномиальные, экспоненциальные, аппроксимативные) для этого? Известна ли сложность?

Гленкора Боррадайле
источник
2
Добро пожаловать, отличный блог !
ВЗН

Ответы:

6

Для разрозненных одномерных областей с целочисленными координатами эквидекомпозиция в минимальное количество кусков является сильно NP-трудной посредством простого сокращения до 3SUM: если одна фигура имеет сегменты, длины которых являются входными данными 3SUM, а другая имеет сегменты, длины которых являются ячейками Вы должны упаковать их, а затем сделать это без дополнительной резки, если экземпляр 3SUM разрешим. Для двумерных полигонов это остается трудным даже для связанных областей: утолщите сегменты одномерной задачи к прямоугольникам единичной высоты и соединяйте их тонкими «струнами», которые имеют слишком малую площадь, чтобы повлиять на 3SUM часть задачи но легко справиться с разложением.

(Отказ от ответственности: я заимствовал эту идею сокращения от некоторой еще не опубликованной совместной работы со многими другими людьми по твердости некоторых других проблем.)

Дэвид Эппштейн
источник
Ваш отказ от ответственности, кажется, на самом деле подтверждение! :-)
Дэвид Ричерби