Сума Мінковського

В геометрії, Сумою Мінковського (англ. minkowski sum) двох множин радіус-векторів A і B у евклідовому просторі утворюється додаванням кожного вектора з A до кожного вектора з B, тобто множина

Червона фігура є сумою синьої та зеленої фігур

${\displaystyle A+B=\{\mathbf {a} +\mathbf {b} \mid \mathbf {a} \in A,\ \mathbf {b} \in B\}.}$

• Сума Мінковського A + B
• B
• A

Приклад

В опуклій оболонці червоної множини, кожна синя точка є опуклою комбінацією якихось червоних точок

Сума Мінковського двох квадратів Q₁=[0,1]² і Q₂=[1,2]² це квадратQ₁+Q₂=[1,3]².

Наприклад, якщо ми маємо дві множини A і B, кожна з трьох радіус-векторів (неформально, трьох точок), що представляють вершини двох трикутників у ${\displaystyle \mathbb {R} ^{2}}$, з координатами

A = {(1, 0), (0, 1), (0, −1)} 

і

B = {(0, 0), (1, 1), (1, −1)} ,

тоді сума Мінковського є
A + B = {(1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)} , яка виглядає як шестикутник, з трьома точками, що повторюються в (1, 0).

Для додавання Мінковського, нульова множина {0}, що містить лише нульовий вектор 0, є нейтральним елементом: Для будь-якої підмножини S, векторного простору

S + {0} = S;

Порожня множина важлива для додавання Мінковського, бо вона знищує будь-яку іншу підмножину: для будь-якої підмножини, S, векторного простору, його сума з порожньою множиною — порожня множина: S + ${\displaystyle \emptyset }$ = ${\displaystyle \emptyset }$.

Прочісування одного опуклого об'єкту іншим

Алгоритм для опуклих многокутників

Кут між вектором ${\displaystyle {\overline {pq}}}$ та віссю ${\displaystyle x.}$

В алгоритмі ми використовуємо поняття кута між вектором ${\displaystyle {\overline {pq}}}$ та віссю ${\displaystyle x.}$

Алгоритм СУМА_МІНКОВСЬКОГО${\displaystyle ({\mathcal {P}},{\mathcal {R}})}$ Вхід. Опуклий многокутник ${\displaystyle {\mathcal {P}}}$ з вершинами ${\displaystyle v_{1},\cdot ,v_{n},}$ і опуклий многокутник ${\displaystyle {\mathcal {R}}}$ з вершинами ${\displaystyle w_{1},\cdots ,w_{m}.}$ Списки вершин повинні бути впорядковані проти годинникової стрілки, а ${\displaystyle v_{1},w_{1}}$ повинні мати найменші ${\displaystyle y}$-координати (і найменші ${\displaystyle x}$-координати у випадку кількох вершин з найменшою ${\displaystyle y}$-координатою). Вихід. Сума Мінковського ${\displaystyle {\mathcal {P}}\oplus {\mathcal {R}}}$. ${\displaystyle i\leftarrow 1;j\leftarrow 1}$ ${\displaystyle v_{n+1}\leftarrow v_{1};v_{n+2}\leftarrow v_{2};w_{m+1}\leftarrow w_{1};w_{m+2}\leftarrow w_{2}}$ повторювати  Додати ${\displaystyle v_{i}+w_{j}}$ як вершину у ${\displaystyle {\mathcal {P}}\oplus {\mathcal {R}}}$.  якщо ${\displaystyle \angle (v_{i}v_{i+1})<\angle (w_{j}w_{j+1})}$  тоді ${\displaystyle i\leftarrow (i+1)}$  інакше якщо ${\displaystyle \angle (v_{i}v_{i+1})>\angle (w_{j}w{j+1})}$   тоді ${\displaystyle j\leftarrow (j+1)}$   інакше ${\displaystyle i\leftarrow (i+1);j\leftarrow (j+1)}$ допоки ${\displaystyle (i=n+1}$ та ${\displaystyle j=m+1)}$

Алгоритм виконується за лінійний час.

Обчислення суми Мінковського для неопуклих многокутників не дуже складне: тріангулювати обидва многокутники, обчислити суму Мінковського для кожної двійки трикутників і об'єднати їх.

Теорема: Нехай ${\displaystyle {\mathcal {P,R}}-}$ многокутники з ${\displaystyle n,m}$ вершинами відповідно. Складність суми Мінковського ${\displaystyle {\mathcal {P}}\oplus {\mathcal {R}}}$ має такі границі:

• це ${\displaystyle O(n+m)}$ якщо обидва многокутники опуклі;
• це ${\displaystyle O(nm)}$ якщо один з многокутників опуклий і один неопуклий;
• це ${\displaystyle O(n^{2}m^{2})}$ якщо обидва многокутники неопуклі.

Ці границі тугі в найгіршому випадку.

Варіації та узагальнення

• Множина сум — аналогічне визначення для підмножин груп у адитивній і арифметичній комбінаториці. Нарівні зі сумами розглядаються множини добутків ${\displaystyle A\times B=\left\lbrace {ab:a\in A,b\in B}\right\rbrace }$ та інші операції.

Посилання

• Hazewinkel, Michiel, ред. (2001), Сума Мінковського, Математична енциклопедія, , ISBN