В геометрії, Сумою Мінковського (англ. minkowski sum) двох множин радіус-векторів A і B у (евклідовому просторі) утворюється додаванням кожного вектора з A до кожного вектора з B, тобто множина
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy90aHVtYi8xLzEwLyVEMCVBMSVEMSU4MyVEMCVCQyVEMCVCQyVEMCVCMF8lRDAlOUMlRDAlQjglRDAlQkQlRDAlQkElRDAlQkUlRDAlQjIlRDElODElRDAlQkElRDAlQkUlRDAlQjMlRDAlQkUuc3ZnLzIyMHB4LSVEMCVBMSVEMSU4MyVEMCVCQyVEMCVCQyVEMCVCMF8lRDAlOUMlRDAlQjglRDAlQkQlRDAlQkElRDAlQkUlRDAlQjIlRDElODElRDAlQkElRDAlQkUlRDAlQjMlRDAlQkUuc3ZnLnBuZw==.png)
- Сума Мінковського A + B
- B
- A
Приклад
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy90aHVtYi84LzhlL0V4dHJlbWVfcG9pbnRzLnN2Zy8yMjBweC1FeHRyZW1lX3BvaW50cy5zdmcucG5n.png)
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy90aHVtYi9kL2RlL01pbmtvd3NraV9zdW0ucG5nLzIyMHB4LU1pbmtvd3NraV9zdW0ucG5n.png)
Наприклад, якщо ми маємо дві множини A і B, кожна з трьох радіус-векторів (неформально, трьох точок), що представляють вершини двох трикутників у , з координатами
- 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 + =
.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvdWsvdGh1bWIvMy8zOC8lRDAlQTElRDElODMlRDAlQkMlRDAlQjBfJUQwJTlDJUQxJTk2JUQwJUJEJUQwJUJBJUQwJUJFJUQwJUIyJUQxJTgxJUQxJThDJUQwJUJBJUQwJUJFJUQwJUIzJUQwJUJFXyVEMCU5RiVEMSU4MCVEMCVCRSVEMSU4NyVEMSU5NiVEMSU4MSVEMSU4MyVEMCVCMiVEMCVCMCVEMCVCRCVEMCVCRCVEMSU4Ri5wbmcvMjIwcHgtJUQwJUExJUQxJTgzJUQwJUJDJUQwJUIwXyVEMCU5QyVEMSU5NiVEMCVCRCVEMCVCQSVEMCVCRSVEMCVCMiVEMSU4MSVEMSU4QyVEMCVCQSVEMCVCRSVEMCVCMyVEMCVCRV8lRDAlOUYlRDElODAlRDAlQkUlRDElODclRDElOTYlRDElODElRDElODMlRDAlQjIlRDAlQjAlRDAlQkQlRDAlQkQlRDElOEYucG5n.png)
Алгоритм для опуклих многокутників
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy90aHVtYi8yLzJkL0FuZ2xlX3BxX3dpdGhfb3gucG5nLzIyMHB4LUFuZ2xlX3BxX3dpdGhfb3gucG5n.png)
В алгоритмі ми використовуємо поняття кута між вектором та віссю
Алгоритм СУМА_МІНКОВСЬКОГО Вхід. Опуклий многокутник Вихід. Сума Мінковського
|
Алгоритм виконується за лінійний час.
Обчислення суми Мінковського для неопуклих многокутників не дуже складне: тріангулювати обидва многокутники, обчислити суму Мінковського для кожної двійки трикутників і об'єднати їх.
Теорема: Нехай многокутники з
вершинами відповідно. Складність суми Мінковського
має такі границі:
- це
якщо обидва многокутники опуклі;
- це
якщо один з многокутників опуклий і один неопуклий;
- це
якщо обидва многокутники неопуклі.
Ці границі тугі в найгіршому випадку.
Варіації та узагальнення
- (Множина сум) — аналогічне визначення для підмножин (груп) у (адитивній) і (арифметичній комбінаториці). Нарівні зі сумами розглядаються множини добутків
та інші операції.
Посилання
- Hazewinkel, Michiel, ред. (2001), Сума Мінковського, (Математична енциклопедія), , ISBN
Ця стаття потребує додаткових для поліпшення її . (липень 2019) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет