Сумма Минковского
Множество всех сумм a+b точек двух тел — основа того, как современные алгоритмы столкновений рассуждают о пересечении.
Сумма A ⊕ B получается, если обвести одну фигуру вдоль границы другой. Для столкновений важна разность A ⊖ B, то есть A ⊕ (−B): тела пересекаются тогда и только тогда, когда эта разность содержит начало координат. Весь вопрос «сталкиваются ли они?» сводится к «лежит ли начало координат внутри одной фигуры?».
Названа в честь Германа Минковского (1864–1909). Для выпуклых многоугольников сумма тоже выпукла и строится за O(n+m) слиянием рёбер, отсортированных по углу. Та же идея лежит в основе планирования движения (препятствия «раздуваются» в конфигурационном пространстве, C-space) и работает внутри и GJK, и EPA.