Учитывая два многогранник и Q , P и Q является равносоставлены , если существует конечные множества многогранников P 1 , ... , P п и Q 1 , ... , Q п таких , что P я и Q я конгруэнтен для всех I , P = ∪ п я = 1 Р я и Q = ∪ п я = 1 Q . Известночто если Р и Q являются многоугольники равной площади, такойequidecompositionвсегда существует и что этоне имеет места в целом для более высоких измерений.
Мне любопытно, что касается сложности проблемы минимального равного состава:
Для двух многоугольников и Q найдите эквивалентную композицию P 1 , … , P n и Q 1 , … , Q n, которая минимизирует n .
Существуют ли алгоритмы (точные, полиномиальные, экспоненциальные, аппроксимативные) для этого? Известна ли сложность?
ds.algorithms
computational-geometry
polygon
Гленкора Боррадайле
источник
источник
Ответы:
Для разрозненных одномерных областей с целочисленными координатами эквидекомпозиция в минимальное количество кусков является сильно NP-трудной посредством простого сокращения до 3SUM: если одна фигура имеет сегменты, длины которых являются входными данными 3SUM, а другая имеет сегменты, длины которых являются ячейками Вы должны упаковать их, а затем сделать это без дополнительной резки, если экземпляр 3SUM разрешим. Для двумерных полигонов это остается трудным даже для связанных областей: утолщите сегменты одномерной задачи к прямоугольникам единичной высоты и соединяйте их тонкими «струнами», которые имеют слишком малую площадь, чтобы повлиять на 3SUM часть задачи но легко справиться с разложением.
(Отказ от ответственности: я заимствовал эту идею сокращения от некоторой еще не опубликованной совместной работы со многими другими людьми по твердости некоторых других проблем.)
источник