Дополнение Минковского - Minkowski addition

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

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

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

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

${\ 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].}$

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

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

Пример

Минковский сложение наборов. Сумма квадратов и квадрат${\ Displaystyle Q_ {1} = [0,1] ^ {2}}$${\ Displaystyle Q_ {2} = [1,2] ^ {2}}$${\ displaystyle Q_ {1} + Q_ {2} = [1,3] ^ {2}.}$

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

B

А

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

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

а также

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

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

${\ Displaystyle A + B = \ {(1,0), (2,1), (2, -1), (0,1), (1,2), (1,0), (0, - 1), (1,0), (1, -2) \}}$

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

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

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

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

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

В качестве другого примера рассмотрит сумму Минковской открытых или закрытых шаров в области , которая является либо действительными числами или комплексных чисел Если это замкнутый шар радиуса с центром в точке , в то для любого , а также будет иметь место для любого скаляра , что произведение является определено (что происходит, когда или ). Если и все ненулевые, то те же равенства все равно выполнялись бы, если бы был определен открытый шар, а не закрытый шар с центром в (требуется ненулевое предположение, потому что открытый шар радиуса является пустым множеством) . Сумма Минковского закрытого шара и открытого шара является открытым шаром. В более общем смысле сумма Минковского открытого подмножества с любым другим набором будет открытым подмножеством. ${\ displaystyle \ mathbb {K},}$ ${\ Displaystyle \ mathbb {R}}$ ${\ displaystyle \ mathbb {C}.}$${\ Displaystyle B_ {r}: = \ {s \ in \ mathbb {K}: | s | \ leq r \}}$${\ Displaystyle г \ в [0, \ infty]}$${\ displaystyle 0}$${\ Displaystyle \ mathbb {K}}$${\ displaystyle r, s \ in [0, \ infty],}$ ${\ displaystyle B_ {r} + B_ {s} = B_ {r + s}}$${\ displaystyle cB_ {r} = B_ {| c | r}}$${\ displaystyle c \ in \ mathbb {K}}$${\ displaystyle | c | r}$${\ displaystyle c \ neq 0}$${\ Displaystyle г \ neq \ infty}$${\ displaystyle r, s,}$${\ displaystyle c}$${\ displaystyle B_ {r}}$${\ displaystyle 0}$${\ displaystyle 0}$

Если это на график из и , если и является ось в то сумма Минковского этих двух замкнутых подмножеств плоскости является открытое множество , состоящее из всего прочего , чем ось. Это показывает, что сумма Минковского двух замкнутых множеств не обязательно является замкнутым множеством. Однако сумма Минковского двух замкнутых подмножеств будет замкнутым подмножеством, если хотя бы одно из этих множеств также является компактным подмножеством . ${\ Displaystyle G = \ left \ {\ left (x, 1 / x \ right): 0 \ neq x \ in \ mathbb {R} \ right \}}$${\ displaystyle f (x) = {\ frac {1} {x}}}$${\ Displaystyle Y = \ {0 \} \ times \ mathbb {R}}$${\ displaystyle y}$${\ Displaystyle X = \ mathbb {R} ^ {2}}$ ${\ displaystyle G + Y = \ {(x, y) \ in \ mathbb {R} ^ {2}: x \ neq 0 \} = \ mathbb {R} ^ {2} \ setminus Y}$${\ displaystyle y}$

Выпуклые оболочки сумм Минковского

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

Для всех непустых подмножеств и реального векторного пространства выпуклая оболочка их суммы Минковского является суммой Минковского их выпуклых оболочек: ${\ displaystyle S_ {1}}$${\ displaystyle S_ {2}}$

${\ 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}).}$

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

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

${\ Displaystyle \ мю S + \ лямбда S = (\ мю + \ лямбда) S}$

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

Пример невыпуклого множества, такого что ${\ displaystyle A + A \ neq 2A.}$

На рисунке справа показан пример невыпуклого множества, для которого ${\ Displaystyle A + A \ supsetneq 2A.}$

Пример в измерении: это легко вычислить, но, следовательно, опять же${\ displaystyle 1}$${\ Displaystyle B = [1,2] \ чашка [4,5].}$${\ displaystyle 2B = [2,4] \ чашка [8,10]}$${\ Displaystyle В + В = [2,4] \ чашка [5,7] \ чашка [8,10],}$${\ Displaystyle B + B \ supsetneq 2B.}$

Суммы Минковского действуют линейно на периметре двумерных выпуклых тел: периметр суммы равен сумме периметров. Кроме того, если это (внутренняя часть) кривая постоянной ширины , то сумма Минковского и ее вращения представляет собой диск. Эти два факта можно объединить, чтобы дать краткое доказательство теоремы Барбье о периметре кривых постоянной ширины. ${\ displaystyle K}$${\ displaystyle K}$${\ displaystyle 180 ^ {\ circ}}$

Приложения

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

Планирование движения

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

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

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

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

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

Теория агрегирования

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

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

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

Алгоритмы вычисления сумм Минковского

Сложение Минковского и выпуклые оболочки. Шестнадцать темно-красных точек (справа) образуют сумму Минковского четырех невыпуклых множеств (слева), каждое из которых состоит из пары красных точек. Их выпуклые корпуса (заштрихованные розовым цветом) содержат знаки плюса (+): правый знак плюс - это сумма левых знаков плюса.

Плоский корпус

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

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

Другой

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

Существенная сумма Минковского

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

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

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

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

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

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

видно, что

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

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

L ^p сумма Минковского

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

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

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

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

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

Смотрите также

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

Заметки

Рекомендации

• Эрроу, Кеннет Дж .; Хан, Фрэнк Х. (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
• Применение дополнения Минковского к робототехнике Джоан Джерард