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

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

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

$A+B=\{𝐚+𝐛\mid 𝐚\in A,𝐛\in B\}.$

• 
  Сума Мінковського Шаблон:Math
• 
  B
• 
  A

Приклад

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

Сума Мінковського двох квадратів Q₁=Шаблон:Closed-closed² і Q₂=Шаблон:Closed-closed² це квадратQ₁+Q₂=Шаблон:Closed-closed².

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

Шаблон:Math

і

Шаблон:Math,

тоді сума Мінковського є
Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math, яка виглядає як шестикутник, з трьома точками, що повторюються в Шаблон:Math.

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

S + {0} = S;

Порожня множина важлива для додавання Мінковського, бо вона знищує будь-яку іншу підмножину: для будь-якої підмножини, S, векторного простору, його сума з порожньою множиною — порожня множина: Шаблон:Math.

Файл:Сума Мінковського Прочісування.png

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

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

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

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

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

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

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

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

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

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

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

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

Посилання

• Шаблон:Springer