Уменьшить разницу Минковского только до вершин корпуса?

Question

Скажем, у нас есть два многогранника, есть ли эффективные способы вычисления только вершин, которые находятся на оболочке разности Минковского?

Я знаю, что для получения одной вершины корпуса вы найдете самую дальнюю вершину в одном многограннике в направлении A, а затем самую дальнюю вершину в другом направлении -A. Но сделать это для каждой вершины было бы по крайней мере O (N ^ 2). Есть ли более эффективный способ?

Answer 1

Существует эффективный метод вычисления суммы Минковского (а следовательно, и разности) выпуклых многогранников.Это описано, например, здесь .Она линейна по числу ребер двух многогранников.

Поскольку для любых точечных множеств выпуклая оболочка их суммы Минковского является суммой Минковского их выпуклых оболочек, вы можете сначала вычислить выпуклые оболочкис алгоритмом Чана), а затем выполните суммирование Минковского.