Сложение Минковского

Красная фигура - это сумма Минковского синих и зеленых фигур.

В геометрии , то сумма Минковская (также известная как дилатация ) из двух наборов из векторов позиции А и В в евклидове пространства формируются путем добавления каждого вектора в А к каждому вектору B , т.е. множество

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

Аналогично, разность Минковского (или геометрическая разность) ^[1] определяется с помощью операции дополнения как

${\ Displaystyle AB = \ влево (A ^ {c} + (- B) \ right) ^ {c}}$

В общем . Например, в одномерном случае и разности Минковского , тогда как${\ Displaystyle AB \ neq A + (- B)}$${\ displaystyle A = [- 2,2]}$${\ displaystyle B = [- 1,1]}$${\ displaystyle AB = [- 1,1]}$${\ Displaystyle A + (- B) = A + B = [- 3,3].}$

В двумерном случае разница Минковского тесно связана с эрозией (морфологией) при обработке изображений .

Сумма Минковского A + B

B

А

Концепция названа в честь Германа Минковского .

Пример [ править ]

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

${\ Displaystyle А = \ {(1,0), (0,1), (0, -1) \}}$

а также

${\ Displaystyle В = \ {(0,0), (1,1), (1, -1) \}}$

то их сумма Минковского равна

${\ Displaystyle А + В = \ {(1,0), (2,1), (2, -1), (0,1), (1,2), (1,0), (0, - 1), (1,0), (1, -2) \}}$

который состоит из вершин шестиугольника.

Для сложения Минковского нулевое множество , {0}, содержащее только нулевой вектор , 0, является единичным элементом : для каждого подмножества S векторного пространства

${\ Displaystyle S + \ {0 \} = S.}$

Пустое множество имеет важное значение в дополнении Минковского, так как пустое множество аннулирует все остальные подмножества: для каждого подмножества S векторного пространства, его сумма с пустым множеством пусто:

${\ displaystyle S + \ emptyset = \ emptyset.}$

В выпуклой оболочке красного множества каждая синяя точка представляет собой выпуклую комбинацию некоторых красных точек.

Минковский сложение наборов. Сумма квадратов Q ₁ = [0,1] ² и Q ₂ = [1,2] ² составляет квадрат Q ₁ + Q ₂ = [1,3] ² .

Выпуклые оболочки сумм Минковского [ править ]

Сложение Минковского хорошо себя ведет по отношению к операции взятия выпуклой оболочки , как показано следующим утверждением:

Для всех непустых подмножеств S ₁ и S ₂ вещественного векторного пространства, выпуклая оболочка их сумм Минковского сумма Минковского выпуклых оболочек:

${\ displaystyle \ operatorname {Conv} (S_ {1} + S_ {2}) = \ operatorname {Conv} (S_ {1}) + \ operatorname {Conv} (S_ {2}).}$

Этот результат верен в более общем случае для любого конечного набора непустых множеств:

${\displaystyle \operatorname {Conv} \left(\sum {S_{n}}\right)=\sum \operatorname {Conv} (S_{n}).}$

В математической терминологии операции суммирования Минковского и формирования выпуклой оболочки являются коммутирующими операциями. ^{[2] [3]}

Если S - выпуклое множество, то также выпуклое множество; более того ${\displaystyle \mu S+\lambda S}$

${\displaystyle \mu S+\lambda S=(\mu +\lambda )S}$

для каждого . И наоборот, если это « свойство распределения » выполняется для всех неотрицательных действительных чисел , то множество выпукло. ^[4]${\displaystyle \mu ,\lambda \geq 0}$${\displaystyle \mu ,\lambda }$

На рисунке показан пример невыпуклого набора , для которого A + A ⊋ 2 .

Пример в одном измерении: B = [1,2] ∪ [4,5] . Легко вычислить, что 2 B = [2,4] ∪ [8,10], но B + B = [2,4] ∪ [5,7] ∪ [8,10] , следовательно, снова B + B ⊋ 2 B .

Суммы Минковского действуют линейно на периметре двумерных выпуклых тел: периметр суммы равен сумме периметров. Кроме того, если K (внутренняя часть) кривой постоянной ширины , тогда сумма Минковского K и ее поворота на 180 ° представляет собой диск. Эти два факта можно объединить, чтобы дать краткое доказательство теоремы Барбье о периметре кривых постоянной ширины. ^[5]

Приложения [ править ]

Сложение Минковского играет центральную роль в математической морфологии . Он возникает в парадигме « кисть и мазок» в компьютерной 2D-графике (с различным использованием, в частности, Дональдом Э. Кнутом в Metafont ), и как непрерывная операция развертки трехмерной компьютерной графики . Также было показано, что он тесно связан с расстоянием до земного движителя и, следовательно, с оптимальной транспортировкой . ^[6]

Планирование движения [ править ]

Суммы Минковского используются при планировании движения объекта среди препятствий. Они используются для вычисления конфигурационного пространства , которое представляет собой набор всех допустимых положений объекта. В простой модели поступательного движения объекта в плоскости, где положение объекта может быть однозначно задано положением неподвижной точки этого объекта, пространство конфигурации представляет собой сумму Минковского множества препятствий и подвижного объекта. объект помещен в начало координат и повернут на 180 градусов.

Обработка с числовым программным управлением (ЧПУ) [ править ]

При обработке с числовым программным управлением программирование инструмента с ЧПУ использует тот факт, что сумма Минковского режущей детали с ее траекторией дает форму выреза в материале.

3D твердотельное моделирование [ править ]

В OpenSCAD суммы Минковского используются, чтобы очертить фигуру с другой фигурой, создавая композицию обеих фигур.

Теория агрегирования [ править ]

Суммы Минковского также часто используются в теории агрегирования, когда отдельные объекты, подлежащие агрегированию, характеризуются посредством множеств. ^{[7] [8]}

Обнаружение столкновений [ править ]

Суммы Минковского, особенно различия Минковского, часто используются вместе с алгоритмами GJK для вычисления обнаружения столкновений для выпуклых корпусов в физических движках .

Алгоритмы вычисления сумм Минковского [ править ]

Планарный случай [ править ]

Два выпуклых многоугольника на плоскости [ править ]

Для двух выпуклых многоугольников P и Q на плоскости с m и n вершинами их сумма Минковского представляет собой выпуклый многоугольник с не более чем m + n вершинами и может быть вычислена за время O ( m + n ) с помощью очень простой процедуры, которая может неформально описать следующим образом. Предположим, что края многоугольника заданы и направление, скажем, против часовой стрелки, вдоль границы многоугольника. Тогда легко увидеть, что эти ребра выпуклого многоугольника упорядочены по полярному углу . Давайте объединить упорядоченные последовательности из ориентированных ребер из P и Qв единую упорядоченную последовательности S . Представьте, что эти края представляют собой сплошные стрелки, которые можно свободно перемещать, сохраняя при этом их параллельность своему первоначальному направлению. Соберите эти стрелки в порядке последовательности S , прикрепив конец следующей стрелки к головке предыдущей. Оказывается, что в результате ломаная будет фактически выпуклый многоугольник , который является суммой Минковского P и Q .

Другое [ править ]

Если один многоугольник выпуклый, а другой - нет, сложность их суммы Минковского составляет O (nm). Если оба они невыпуклые, сложность их суммы Минковского равна O ((mn) ² ).

Основная сумма Минковского [ править ]

Существует также понятие существенной суммы Минковского + _e двух подмножеств евклидова пространства. Обычная сумма Минковского может быть записана как

${\displaystyle A+B=\left\{z\in \mathbb {R} ^{n}\,|\,A\cap (z-B)\neq \emptyset \right\}.}$

Таким образом, существенная сумма Минковского определяется равенством

${\displaystyle A+_{\mathrm {e} }B=\left\{z\in \mathbb {R} ^{n}\,|\,\mu \left[A\cap (z-B)\right]>0\right\},}$

где μ обозначает n -мерную меру Лебега . Причиной появления термина «существенный» является следующее свойство индикаторных функций : в то время как

${\displaystyle 1_{A\,+\,B}(z)=\sup _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

видно, что

${\displaystyle 1_{A\,+_{\mathrm {e} }\,B}(z)=\mathop {\mathrm {ess\,sup} } _{x\,\in \,\mathbb {R} ^{n}}1_{A}(x)1_{B}(z-x),}$

где "ess sup" обозначает существенную верхнюю грань .

L ^р Минковский сумма [ править ]

Для K и L компактных выпуклых подмножеств , сумма Минковского может быть описана функцией поддержки выпуклых множеств:${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle h_{K+L}=h_{K}+h_{L}.}$

Для р ≥ 1 , Фиря ^[9] определена л ^р Минковского суммы К + _р л компактных выпуклых множества K и L в содержащем начало координат${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle h_{K+_{p}L}^{p}=h_{K}^{p}+h_{L}^{p}.}$

По неравенству Минковского , функция ч _{К + р L} снова положительно однородна и выпукла и , следовательно , опорная функция компакта выпуклой. Это определение является фундаментальным в L ^р теории Брун-Минковского.

См. Также [ править ]

• Сумма Бляшке
• Теорема Брунна – Минковского , неравенство об объемах сумм Минковски.
• Свертка
• Расширение
• Эрозия
• Интервальная арифметика
• Смешанный объем (также известный как Quermassintegral или собственный объем )
• Параллельная кривая
• Лемма Шепли – Фолкмана.
• Топологическое векторное пространство # Свойства
• Зонотоп

Заметки [ править ]

Ссылки [ править ]

• Эрроу, Кеннет Дж .; Хан, Фрэнк Х. (1980). Общий конкурентный анализ . Учебники по экономике. 12 (перепечатка (1971) Сан-Франциско, Калифорния: Holden-Day, Inc. Тексты по математической экономике.  6  изд.). Амстердам: Северная Голландия. ISBN 978-0-444-85497-1. Руководство по ремонту  0439057 .
• Гарднер, Ричард Дж. (2002), "Неравенство Брунна-Минковского", Бюлл. Амер. Математика. Soc. (NS) , 39 (3): 355-405 (электронный), DOI : 10,1090 / S0273-0979-02-00941-2
• Грин, Джерри; Хеллер, Уолтер П. (1981). «1 Математический анализ и выпуклость с приложениями к экономике». In Arrow, Кеннет Джозеф ; Интрилигатор, Майкл Д. (ред.). Справочник по математической экономике, Том  I. Справочники по экономике. 1 . Амстердам: Издательство Северной Голландии, стр. 15–52. DOI : 10.1016 / S1573-4382 (81) 01005-9 . ISBN 978-0-444-86126-9. Руководство по ремонту  0634800 .
• Генри Манн (1976), Теоремы сложения: теоремы сложения теории групп и теории чисел (исправленное переиздание 1965 года, изд. Wiley), Хантингтон, Нью-Йорк: издательство Robert E. Krieger Publishing Company, ISBN 978-0-88275-418-5- через http://www.krieger-publishing.com/subcats/Mat MathematicsandStatistics/ mat Mathematicsandstatistics.html.
• Рокафеллар, Р. Тиррелл (1997). Выпуклый анализ . Вехи Принстона в математике (Перепечатка Принстонской математической серии 1979 г.,  28-  е изд.). Принстон, Нью-Джерси: Издательство Принстонского университета. С. xviii + 451. ISBN 978-0-691-01586-6. Руководство по ремонту  1451876 .
• Натансон, Мелвин Б. (1996), Аддитивная теория чисел: обратные задачи и геометрия сумм , GTM, 165 , Springer, Zbl  0859.11003.
• Окс, Эдуард; Шарир, Миха (2006), "Суммы Минковского монотонных и общих простых многоугольников", Дискретная и вычислительная геометрия , 35 (2): 223-240, DOI : 10.1007 / s00454-005-1206-й.
• Шнайдер, Рольф (1993), Выпуклые тела: теория Брунна-Минковского , Кембридж: Издательство Кембриджского университета.
• Тао, Теренс и Ву, Ван (2006), Аддитивная комбинаторика , Cambridge University Press.
• Mayer, A .; Зеленюк, В. (2014). «Агрегация показателей производительности Мальмквиста с учетом перераспределения ресурсов» . Европейский журнал операционных исследований . 238 (3): 774–785. DOI : 10.1016 / j.ejor.2014.04.003 .
• Зеленюк, В (2015). «Агрегирование масштабной эффективности» . Европейский журнал операционных исследований . 240 (1): 269–277. DOI : 10.1016 / j.ejor.2014.06.038 .

Внешние ссылки [ править ]

• «Сложение Минковского» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Хоу, Роджер (1979), О тенденции к выпуклости векторной суммы множеств , дискуссионные документы Фонда Коулза, 538 , Фонд Каулза для исследований в области экономики , Йельский университет
• Суммы Минковского в библиотеке алгоритмов вычислительной геометрии
• Сумма Минковского двух треугольников и сумма Минковского диска и многоугольника Джорджа Бека, The Wolfram Demonstrations Project .
• Добавление Минковского выпуклых фигур с помощью Александра Богомольного : апплет
• Wikibooks: OpenSCAD User Manual / Transformations # minkowski by Marius Kintel: Application