В геометрії, Сумою Мінковського () двох множин радіус-векторів A і B у евклідовому просторі утворюється додаванням кожного вектора з A до кожного вектора з B, тобто множина
Приклад
Наприклад, якщо ми маємо дві множини A і B, кожна з трьох радіус-векторів (неформально, трьох точок), що представляють вершини двох трикутників у , з координатами
і
,
тоді сума Мінковського є , , , , , , , , , яка виглядає як шестикутник, з трьома точками, що повторюються в .
Для додавання Мінковського, нульова множина {0}, що містить лише нульовий вектор 0, є нейтральним елементом: Для будь-якої підмножини S, векторного простору S + {0} = S;
Порожня множина важлива для додавання Мінковського, бо вона знищує будь-яку іншу підмножину: для будь-якої підмножини, S, векторного простору, його сума з порожньою множиною — порожня множина: .
Алгоритм для опуклих многокутників
В алгоритмі ми використовуємо поняття кута між вектором та віссю
Алгоритм СУМА_МІНКОВСЬКОГО
Вхід. Опуклий многокутник з вершинами і опуклий многокутник з вершинами Списки вершин повинні бути впорядковані проти годинникової стрілки, а повинні мати найменші -координати (і найменші -координати у випадку кількох вершин з найменшою -координатою).
Вихід. Сума Мінковського .
повторювати Додати як вершину у . якщо тоді інакше якщо тоді інакше допоки та
Алгоритм виконується за лінійний час.
Обчислення суми Мінковського для неопуклих многокутників не дуже складне: тріангулювати обидва многокутники, обчислити суму Мінковського для кожної двійки трикутників і об'єднати їх.
Теорема: Нехай многокутники з вершинами відповідно. Складність суми Мінковського має такі границі: це якщо обидва многокутники опуклі; це якщо один з многокутників опуклий і один неопуклий; це якщо обидва многокутники неопуклі. Ці границі тугі в найгіршому випадку.
Варіації та узагальнення Множина сум — аналогічне визначення для підмножин груп у адитивній і арифметичній комбінаториці. Нарівні зі сумами розглядаються множини добутків та інші операції.
Посилання