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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Червона фігура є сумою синьої та зеленої фігур

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

A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.

Приклад[ред.ред. код]

Картинка згладженого трикутника. Кожен з округлих кутів обведений червоною кривою.
В опуклій оболонці червоної множини, кожна синя точка є опуклою комбінацією якихось червоних точок
Сума Мінковського двох квадратів Q1=[0,1]2 і Q2=[1,2]2 це квадратQ1+Q2=[1,3]2.

Наприклад, якщо ми маємо дві множини A і B, кожна з трьох радіус-векторів (неформально, трьох точок), що представляють вершини двох трикутників у \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 + \emptyset = \emptyset.

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

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

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

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

Алгоритм СУМА_МІНКОВСЬКОГО(\mathcal{P}, \mathcal{R})

Вхід. Опуклий многокутник \mathcal{P} з вершинами v_1, \cdot ,v_n, і опуклий многокутник \mathcal{R} з вершинами w_1, \cdots ,w_m. Списки вершин повинні бути впорядковані прости годинникової стрілки, а v_1, w_1 повинні мати найменші y-координати (і найменші x-координати у випадку кількох вершин з найменшою y-координатою).

Вихід. Сума Мінковського \mathcal{P}\oplus\mathcal{R}.

  1. i\leftarrow 1; j\leftarrow 1
  2. v_{n+1}\leftarrow v_1; v_{n+2}\leftarrow v_2; w_{m+1}\leftarrow w_1; w_{m+2}\leftarrow w_2
  3. повторювати
  4.  Додати v_i+w_j як вершину у \mathcal{P}\oplus\mathcal{R}.
  5. якщо \angle(v_iv_{i+1}) < \angle(w_jw_{j+1})
  6. тоді i\leftarrow(i+1)
  7. інакше якщо \angle(v_iv_{i+1}) > \angle(w_jw{j+1})
  8.   тоді j\leftarrow( j+1)
  9.   інакше i\leftarrow(i+1); j\leftarrow(j+1)
  10. допоки (i = n+1 та j = m+1)

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

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

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

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

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

Посилання[ред.ред. код]