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

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

Ключевые слова: геометрическая оптимизация, размещение многогранников, суммы Минковского, растеризация, численные методы, сложность вычислений.

Название статьи, аннотация и ключевые слова на английском языке

  • Карпухин С.А. – Московский государственный университет им. М.В. Ломоносова, механико-математический факультет, Ленинские горы, 119899, Москва; аспирант, e-mail: ks-linp@yandex.ru