О сложности геометрической оптимизации методом растеризации сумм Минковского

Рассматривается задача поиска наибольшего многогранника заданной формы (шаблона) внутри другого многогранника и численный метод ее решения при фиксированной ориентации шаблона, основанный на растеризации сумм Минковского. Исследуется сложность данного метода в случае задачи с выпуклым шаблоном и единственным решением в трехмерном пространстве. Доказана ограниченность используемой в алгоритме сетки вне зависимости от точности решения. Выведена теоретическая оценка сверху времени работы алгоритма. Полученная оценка проверена на практической реализации метода.