Dodatek Minkowskiego - Minkowski addition

Czerwona cyfra to suma Minkowskiego cyfr niebieskich i zielonych.

W geometrii The suma Minkowskiego (znany również jako rozszerzenie ) dwóch zestawów z wektorów pozycji A i B w przestrzeni euklidesowej jest utworzony przez dodanie każdego wektora w A do każdego wektora w B , to jest zestaw

${\ Displaystyle A + B = \ {\ mathbf {a} + \ mathbf {b} \, | \, \ mathbf {a} \ w A \ \ mathbf {b} \ w B \}.}$

Analogicznie różnicę Minkowskiego (lub różnicę geometryczną) definiuje się za pomocą operacji dopełnienia jako

${\ Displaystyle AB = \ lewo (A ^ {c} + (-B) \ po prawej) ^ {c}}$

Ogólnie . Na przykład w przypadku jednowymiarowym i różnicy Minkowskiego , natomiast${\displaystyle AB\neq A+(-B)}$${\displaystyle A=[-2,2]}$${\displaystyle B=[-1,1]}$${\displaystyle AB=[-1,1]}$${\ Displaystyle A + (-B) = A + B = [-3,3].}$

W przypadku dwuwymiarowym różnica Minkowskiego jest ściśle związana z erozją (morfologią) w przetwarzaniu obrazu .

Koncepcja nosi imię Hermanna Minkowskiego .

Przykład

Minkowskiego dodawanie zestawów. Suma kwadratów i jest kwadratem${\displaystyle Q_{1}=[0,1]^{2}}$${\displaystyle Q_{2}=[1,2]^{2}}$${\displaystyle Q_{1}+Q_{2}=[1,3]^{2}.}$

Suma Minkowskiego A + B

b

ZA

Na przykład, jeśli mamy dwa zbiory A i B , każdy składający się z trzech wektorów położenia (nieformalnie trzech punktów), reprezentujących wierzchołki dwóch trójkątów w , o współrzędnych ${\ Displaystyle \ mathbb {R} ^ {2}}$

${\displaystyle A=\{(1,0),(0,1),(0,-1)\}}$

i

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

to ich suma Minkowskiego wynosi

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

który zawiera wierzchołki sześciokąta.

Dla dodania Minkowskiego zbiór zer , zawierający tylko wektor zerowy , 0, jest elementem identyczności : dla każdego podzbioru S przestrzeni wektorowej, ${\displaystyle \{0\},}$

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

Zbiór pusty jest ważne Minkowskiego Ponadto, ponieważ pusty zestaw niszczy co drugi podzbiór: dla każdego podzbioru S w przestrzeni wektorowej, ich suma z pustego zestawu jest puste:

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

Jako inny przykład rozważ sumy Minkowskiego otwartych lub zamkniętych kul w polu, które są albo liczbami rzeczywistymi albo liczbami zespolonymi Jeśli jest kulą zamkniętą o promieniu o środku w to dla dowolnego i będzie również obowiązywać dla dowolnego skalara tak że iloczyn jest zdefiniowane (co dzieje się, gdy lub ). Jeśli i wszystkie są niezerowe, to te same równości nadal by były zdefiniowane jako otwarta kula, a nie zamknięta kula, wyśrodkowana (założenie niezerowe jest potrzebne, ponieważ otwarta kula o promieniu jest zbiorem pustym) . Suma Minkowskiego kuli zamkniętej i kuli otwartej jest kulą otwartą. Bardziej ogólnie, suma Minkowskiego podzbioru otwartego z dowolnym innym zbiorem będzie podzbiorem otwartym. ${\ Displaystyle \ mathbb {K} ,}$ ${\ Displaystyle \ mathbb {R}}$ ${\ Displaystyle \ mathbb {C}.}$${\ Displaystyle B_ {R}: = \ {s \ w \ mathbb {K}: | s | \ leq r \}}$${\displaystyle r\w [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 \ w \ mathbb {K} }$${\displaystyle |c|r}$${\displaystyle c\neq 0}$${\displaystyle r\neq \infty}$${\displaystyle r,s,}$${\displaystyle c}$${\displaystyle B_{r}}$${\ Displaystyle 0}$${\ Displaystyle 0}$

Jeśli jest wykres z , a jeśli i to -działający w czym suma Minkowskiego tych dwóch zamkniętych podzbiorów płaszczyzny jest otwarty zestaw składający się z wszystkiego innego niż -działający. To pokazuje, że suma Minkowskiego dwóch zbiorów domkniętych niekoniecznie jest zbiorem domkniętym. Jednak suma Minkowskiego dwóch zamkniętych podzbiorów będzie podzbiorem domkniętym, jeśli przynajmniej jeden z tych zbiorów jest również podzbiorem zwartym . ${\ Displaystyle G = \ lewo \ {\ lewo (x, 1 / x \ po prawej): 0 \ neq x \ w \ mathbb {R} \ po prawej \}}$${\ Displaystyle f (x) = {\ Frac {1} {x}}}$${\ Displaystyle Y = \ {0 \} \ razy \ mathbb {R}}$${\displaystyle y}$${\ Displaystyle X = \ mathbb {R} ^ {2}}$ ${\ Displaystyle G + Y = \ {(x, y) \ w \ mathbb {R} ^ {2}: x \ neq 0 \} = \ mathbb {R} ^ {2} \ setminus Y}$${\displaystyle y}$

Wypukłe łuski sum Minkowskiego

Dodatek Minkowskiego dobrze zachowuje się w odniesieniu do operacji przyjmowania łusek wypukłych , o czym świadczy następująca propozycja:

Dla wszystkich niepustych podzbiorów i rzeczywistej przestrzeni wektorowej powłoka wypukła ich sum Minkowskiego jest sumą Minkowskiego ich powłok wypukłych: ${\displaystyle S_{1}}$${\displaystyle S_{2}}$

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

Ten wynik jest bardziej ogólny dla każdego skończonego zbioru niepustych zbiorów:

${\ Displaystyle \ Operatorname {Conv} \ left (\ suma {S_ {n}} \ right) = \ suma \ operatorname {Conv} (S_ {n}).}$

W terminologii matematycznej operacje sumowania Minkowskiego i formowania wypukłych kadłubów są operacjami przemiennymi .

Jeśli jest zbiorem wypukłym, to także jest zbiorem wypukłym; Ponadto ${\displaystyle S}$${\ Displaystyle \ mu S + \ lambda S}$

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

dla każdego . I odwrotnie, jeśli ta „ własność rozdzielcza ” obowiązuje dla wszystkich nieujemnych liczb rzeczywistych , to zbiór jest wypukły. ${\ Displaystyle \ mu \ lambda \ geq 0}$${\displaystyle \mu,\lambda}$

Przykład zbioru niewypukłego takiego, że ${\displaystyle A+A\neq 2A.}$

Rysunek po prawej pokazuje przykład zestawu niewypukłego, dla którego ${\ Displaystyle A + A \ supsetneq 2A.}$

Przykładem w wymiarze jest: Można to łatwo obliczyć, ale stąd znowu${\ Displaystyle 1}$${\ Displaystyle B = [1,2] \ filiżanka [4,5].}$${\ Displaystyle 2B = [2,4] \ filiżanka [8,10]}$${\ Displaystyle B + B = [2,4] \ filiżanka [5,7] \ filiżanka [8,10],}$${\ Displaystyle B + B \ supsetneq 2B.}$

Sumy Minkowskiego działają liniowo na obwodzie dwuwymiarowych ciał wypukłych: obwód sumy jest równy sumie obwodów. Dodatkowo, jeśli jest (wnętrzem) krzywą o stałej szerokości , to suma Minkowskiego i jej obrotu jest dyskiem. Te dwa fakty można połączyć, aby uzyskać krótki dowód twierdzenia Barbiera o obwodzie krzywych o stałej szerokości. ${\ Displaystyle K}$${\ Displaystyle K}$${\displaystyle 180^{\circ}}$

Aplikacje

Dodatek Minkowskiego odgrywa kluczową rolę w morfologii matematycznej . Powstaje w szczotki i udaru paradygmacie z 2D grafiki komputerowej (z różnych zastosowań, w szczególności przez Donald E. Knuth w mEtaFoNt-a ), jak i w stałych przemiatania operacji komputerowych 3D grafiki . Wykazano również, że jest ściśle powiązany z odległością poruszacza Ziemi , a co za tym idzie, optymalnym transportem .

Planowanie ruchu

Sumy Minkowskiego wykorzystywane są w planowaniu ruchu obiektu wśród przeszkód. Służą do obliczania przestrzeni konfiguracyjnej , która jest zbiorem wszystkich dopuszczalnych pozycji obiektu. W prostym modelu ruchu postępowego obiektu w płaszczyźnie, w którym położenie obiektu może być jednoznacznie określone położeniem stałego punktu tego obiektu, przestrzenią konfiguracyjną jest suma Minkowskiego zbioru przeszkód i ruchomego obiekt umieszczony w początku i obrócony o 180 stopni.

Obróbka numeryczna (NC)

W obróbce sterowanej numerycznie programowanie narzędzia NC wykorzystuje fakt, że suma Minkowskiego elementu skrawanego wraz z jego trajektorią daje kształt nacięcia w materiale.

Modelowanie brył 3D

W OpenSCAD Minkowski sumy są używane do obrysowania kształtu innym kształtem, tworząc połączenie obu kształtów.

Teoria agregacji

Sumy Minkowskiego są również często stosowane w teorii agregacji, gdy poszczególne obiekty, które mają zostać zagregowane, są charakteryzowane za pomocą zbiorów.

Wykrywanie kolizji

Sumy Minkowskiego, a konkretnie różnice Minkowskiego, są często używane wraz z algorytmami GJK do obliczania wykrywania kolizji dla wypukłych kadłubów w silnikach fizycznych .

Algorytmy obliczania sum Minkowskiego

Dodatek Minkowskiego i wypukłe łuski. Szesnaście ciemnoczerwonych punktów (po prawej) tworzy sumę Minkowskiego czterech niewypukłych zbiorów (po lewej), z których każdy składa się z pary czerwonych punktów. Ich wypukłe kadłuby (zacieniowane na różowo) zawierają znaki plus (+): Prawy znak plus jest sumą lewych znaków plus.

Przypadek planarny

Dwa wypukłe wielokąty na płaszczyźnie

Dla dwóch wypukłych wielokątów P i Q w płaszczyźnie o m i n wierzchołkach ich suma Minkowskiego jest wielokątem wypukłym o co najwyżej m + n wierzchołkach i może być obliczona w czasie O( m + n ) za pomocą bardzo prostej procedury, która może być nieformalnie opisany w następujący sposób. Załóżmy, że podane są krawędzie wielokąta i kierunek, powiedzmy, przeciwny do ruchu wskazówek zegara, wzdłuż granicy wielokąta. Wtedy łatwo zauważyć, że te krawędzie wielokąta wypukłego są uporządkowane według kąta biegunowego . Połączmy uporządkowane sekwencje skierowanych krawędzi z P i Q w jeden uporządkowany ciąg S . Wyobraź sobie, że te krawędzie to solidne strzałki, które można swobodnie przesuwać, utrzymując je równolegle do pierwotnego kierunku. Połącz te strzały w kolejności sekwencji S , dołączając ogon następnej strzały do ​​grotu poprzedniej strzały. Okazuje się, że otrzymany łańcuch wielokątny będzie w rzeczywistości wielokątem wypukłym, który jest sumą Minkowskiego P i Q .

Inny

Jeśli jeden wielokąt jest wypukły, a drugi nie, złożoność ich sumy Minkowskiego wynosi O(nm). Jeśli oba są niewypukłe, ich złożoność sumy Minkowskiego wynosi O((mn) ² ).

Niezbędna suma Minkowskiego

Istnieje również pojęcie zasadniczej sumy Minkowskiego + _e dwóch podzbiorów przestrzeni euklidesowej. Zwykłą sumę Minkowskiego można zapisać jako

${\ Displaystyle A + B = \ lewo \ {z \ w \ mathbb {R} ^ {n} \ | \ A \ czapka (zB) \ neq \ pusty zestaw \ prawo \}}.$

Zatem zasadnicza suma Minkowskiego jest zdefiniowana przez:

${\ Displaystyle A + _ {\ operatorname {e}} B = \ lewo \ {z \ w \ mathbb {R} ^ {n} \, | \ \ mu \ lewo [A \ czapka (zB) \ prawo] >0\prawo\},}$

gdzie μ oznacza n- wymiarową miarę Lebesgue'a . Powodem terminu „niezbędny” jest następująca właściwość funkcji wskaźnika : while

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

można zauważyć, że

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

gdzie "ess sup" oznacza zasadnicze supremum .

Suma L ^p Minkowskiego

Dla zwartych podzbiorów wypukłych K i L w , sumę Minkowskiego można opisać funkcją wsparcia zbiorów wypukłych: ${\ Displaystyle \ mathbb {R} ^ {n}}$

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

Dla p ≥ 1 , Firey zdefiniował sumę L ^p Minkowskiego K + _p L zwartych zbiorów wypukłych K i L w zawierających pochodzenie jako ${\ Displaystyle \ mathbb {R} ^ {n}}$

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

Dzięki nierówności Minkowskiego funkcja h _{K+ p L} jest znowu dodatnio jednorodna i wypukła, a zatem jest funkcją podporową zwartego zbioru wypukłego. Definicja ta ma podstawowe znaczenie w L ^p teorii Brunn-Minkowskiego.

Zobacz też

• Suma Blaschke
• Twierdzenie Brunna –Minkowskiego , nierówność na objętości sum Minkowskiego
• Skręt
• Rozszerzanie się
• Erozja
• Arytmetyka interwałowa
• Objętość mieszana (inaczej Quermassintegral lub objętość wewnętrzna )
• Krzywa równoległa
• Lemat Shapleya-Folkmana
• Sumset
• Topologiczna przestrzeń wektorowa#Właściwości
• Zonotop

Uwagi

Bibliografia

• Arrow, Kenneth J .; Hahn, Frank H. (1980). Ogólna analiza konkurencji . Zaawansowane podręczniki z ekonomii. 12 (przedruk (1971) San Francisco, CA: Holden-Day, Inc. Teksty z ekonomii matematycznej.  6  wyd.). Amsterdam: Holandia Północna. Numer ISBN 978-0-444-85497-1. MR  0439057 .
• Gardner, Richard J. (2002), "Nierówność Brunna-Minkowskiego", Bull. Amer. Matematyka. Soc. (NS) , 39 (3): 355–405 (elektroniczny), doi : 10.1090/S0273-0979-02-00941-2
• Zielony, Jerry; Heller, Walter P. (1981). „1 Analiza matematyczna i wypukłość z zastosowaniami w ekonomii”. W Arrow, Kenneth Joseph ; Intryligator, Michael D (red.). Podręcznik ekonomii matematycznej, Tom  I. Podręczniki z ekonomii. 1 . Amsterdam: North-Holland Publishing Co. s. 15-52. doi : 10.1016/S1573-4382(81)01005-9 . Numer ISBN 978-0-444-86126-9. Numer MR  0634800 .
• Henry Mann (1976), Twierdzenia o dodawaniu: Twierdzenia o dodawaniu teorii grup i teorii liczb (poprawiony przedruk z 1965 Wiley ed.), Huntington, New York: Robert E. Krieger Publishing Company, ISBN 978-0-88275-418-5– przez http://www.krieger-publishing.com/subcats/MathematicsandStatistics/mathematicsandstatistics.html
• Rockafellar, R. Tyrrell (1997). Analiza wypukła . Zabytki Princeton w matematyce (Przedruk z serii matematycznej Princeton z 1979 r.,  28  ed.). Princeton, NJ: Princeton University Press. s. xviii+451. Numer ISBN 978-0-691-01586-6. MR  1451876 .
• Nathanson, Melvyn B. (1996), Teoria liczb addytywnych: problemy odwrotne i geometria sum , GTM, 165 , Springer, Zbl  0859.11003.
• Oks, Edwardzie; Sharir, Micha (2006), "Minkowski Sums of Monotone and General Simple Polygons", Geometria dyskretna i obliczeniowa , 35 (2): 223-240, doi : 10.1007/s00454-005-1206-y.
• Schneider, Rolf (1993), Ciała wypukłe: teoria Brunna-Minkowskiego , Cambridge: Cambridge University Press.
• Tao, Terence & Vu, Van (2006), Additive Combinatorics , Cambridge University Press.
• Mayer, A.; Zelenyuk, V. (2014). „Agregacja wskaźników produktywności Malmquista pozwalająca na realokację zasobów” . Europejski Dziennik Badań Operacyjnych . 238 (3): 774–785. doi : 10.1016/j.ejor.2014.04.003 .
• Zelenyuk, V (2015). „Agregacja wydajności wagi” . Europejski Dziennik Badań Operacyjnych . 240 (1): 269–277. doi : 10.1016/j.ejor.2014.06.038 .

Linki zewnętrzne

• „Dodatek Minkowskiego” , Encyklopedia Matematyki , EMS Press , 2001 [1994]
• Howe, Roger (1979), O tendencji do wypukłości sumy wektorowej zbiorów , Cowles Foundation discussion papers, 538 , Cowles Foundation for Research in Economics , Yale University
• Sumy Minkowskiego , w bibliotece algorytmów geometrii obliczeniowej
• Suma Minkowskiego dwóch trójkątów i Suma Minkowskiego dysku i wielokąta autorstwa George'a Becka, Projekt Wolfram Demonstrations .
• Dodatek Minkowskiego wypukłych kształtów autorstwa Aleksandra Bogomolnego : aplet
• Wikibooks: Podręcznik użytkownika OpenSCAD/Transformacje#minkowski autorstwa Mariusa Kintela: Aplikacja
• Zastosowanie dodatku Minkowskiego do robotyki Joan Gerard