Изменения

== Описание ==

{|align="center"

|-valign="top"

Пусть заданы две выпуклые фигуры <tex>P</tex> и <tex>R</tex>, с числом вершин <tex>n</tex> и <tex>m</tex> соответственно. Тогда суммой Минковского <tex>P \oplus R</tex> является выпуклая фигура с не более чем <tex>m + n</tex> вершинами.

|proof=

Для начала заметим, что любая крайняя точка в направлении вектора <tex>\vec{d}</tex> есть сумма крайних точек фигур в этом направлении. Убедиться в этом можно спроецировав обе фигуры на вектор <tex>\vec{d}</tex>.

}}

i = j = 0

while i < n or j < m do

add V[i]+W[j] to answer

|[[Файл:minkowski_hard_example.png | thumb | 550px | Пример суммы Минковского с O(n²m²) вершинами]]

|}