Minkowského doplnění - Minkowski addition

v geometrie, Minkowského součet (také známý jako dilatace ) ze dvou sady z polohové vektory A a B v Euklidovský prostor je vytvořen přidáním každého vektoru do A ke každému vektoru v B, tj. sada
Analogicky Minkowski rozdíl (nebo geometrický rozdíl)[1] je definován pomocí provoz doplňku tak jako
Obecně . Například v jednorozměrném případě a rozdíl Minkowski , zatímco
V dvojrozměrném případě je Minkowského rozdíl úzce spjat s eroze (morfologie) v zpracování obrazu.



Koncept je pojmenován pro Hermann Minkowski.
Příklad
Například pokud máme dvě sady A a B, z nichž každý se skládá ze tří polohových vektorů (neformálně, tří bodů), představujících vrcholy ze dvou trojúhelníky v , se souřadnicemi
a
pak je jejich Minkowského součet
který zahrnuje vrcholy šestiúhelníku.
Pro doplnění Minkowski, nulová sada, {0}, obsahující pouze nulový vektor, 0, je prvek identity: pro každou podmnožinu S vektorového prostoru,
The prázdná sada je důležité v Minkowského doplnění, protože prázdná množina ničí všechny ostatní podmnožiny: pro každou podmnožinu S vektorového prostoru je jeho součet s prázdnou množinou prázdný:

![V nezáporném kvadrantu karteziánské roviny jsou zobrazeny tři čtverce. Čtverec Q1 = [0,1] × [0,1] je zelený. Čtverec Q2 = [1,2] × [1,2] je hnědý a nachází se uvnitř tyrkysového čtverce Q1 + Q2 = [1,3] × [1,3].](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Minkowski_sum_graph_-_vector_version.svg/220px-Minkowski_sum_graph_-_vector_version.svg.png)
Konvexní slupky minkowských součtů
Minkowského doplněk se chová dobře s ohledem na operaci převzetí konvexní trupy, jak ukazuje následující návrh:
- Pro všechny neprázdné podmnožiny S1 a S2 skutečného vektorového prostoru je konvexní trup jejich Minkowského součtu Minkowského součet jejich konvexních trupů:
Tento výsledek platí obecněji pro jakoukoli konečnou sbírku neprázdných sad:
V matematické terminologii se operace Minkowského součtu a formování konvexní trupy jsou dojíždění operace.[2][3]
Li S je konvexní množina je také konvexní množina; dále
pro každého . Naopak, pokud toto “distribuční vlastnictví "platí pro všechna nezáporná reálná čísla, , pak je množina konvexní.[4]
Obrázek ukazuje příklad nekonvexní množiny, pro kterou A + A ⊋ 2A.

Příklad v 1 dimenzi je: B= [1,2] ∪ [4,5]. Lze snadno vypočítat, že 2B= [2,4] ∪ [8,10] ale B+B= [2,4] ∪ [5,7] ∪ [8,10], tedy znovu B+B ⊋ 2B.
Minkowského součty působí lineárně na obvod dvourozměrných konvexních těles: obvod součtu se rovná součtu obvodů. Navíc, pokud K. je (vnitřek) a křivka konstantní šířky, pak Minkowského součet K. a jeho otočení o 180 ° je disk. Tyto dvě skutečnosti lze kombinovat a poskytnout krátký důkaz Barbierova věta na obvodu křivek konstantní šířky.[5]
Aplikace
Minkowski doplněk hraje ústřední roli v matematická morfologie. Vzniká v paradigma štětce a tahu z 2D počítačová grafika (s různým použitím, zejména do Donald E. Knuth v Metafont ) a jako pevné zametání provoz 3D počítačová grafika. Ukázalo se také, že je úzce spjat s Vzdálenost pohybujícího se Země, a rozšířením, optimální transport.[6]
Plánování pohybu
Minkowského částky se používají v plánování pohybu objektu mezi překážkami. Používají se pro výpočet konfigurační prostor, což je množina všech přípustných pozic objektu. V jednoduchém modelu translačního pohybu objektu v rovině, kde lze polohu objektu jednoznačně specifikovat polohou pevného bodu tohoto objektu, je konfigurační prostor Minkowského součet množiny překážek a pohyblivých objekt umístěný na počátku a otočený o 180 stupňů.
Obrábění pomocí numerického řízení (NC)
v numerické ovládání obrábění, programování NC nástroje využívá skutečnosti, že Minkowského součet řezný kus svou trajektorií dává tvar řezu v materiálu.
3D modelování těles
v OpenSCAD Minkowského součty se používají k obrysu tvaru s jiným tvarem, který vytváří směsici obou tvarů.
Teorie agregace
Minkowského součty se také často používají v teorii agregace, když jsou jednotlivé objekty, které mají být agregovány, charakterizovány pomocí množin.[7][8]
Detekce kolize
Spolu s nimi se často používají Minkowského součty, konkrétně Minkowského rozdíly Algoritmy GJK počítat Detekce kolize pro konvexní trupy v fyzikální motory.
Algoritmy pro výpočet Minkowského součtů

Rovinný případ
Dva konvexní polygony v rovině
Pro dva konvexní polygony P a Q v letadle s m a n vrcholy, jejich Minkowského součet je konvexní mnohoúhelník s maximálně m + n vrcholy a lze je vypočítat v čase O (m + n) velmi jednoduchým postupem, který lze neformálně popsat následovně. Předpokládejme, že jsou uvedeny hrany mnohoúhelníku a směr, řekněme proti směru hodinových ručiček, podél hranice mnohoúhelníku. Pak je snadno vidět, že tyto hrany konvexního mnohoúhelníku jsou seřazeny podle polární úhel. Dovolte nám sloučit seřazené sekvence směrovaných hran od P a Q do jedné seřazené sekvence S. Představte si, že tyto hrany jsou plné šipky které lze volně pohybovat při zachování jejich rovnoběžnosti s jejich původním směrem. Sestavte tyto šipky v pořadí podle pořadí S připojením ocasu další šipky k hlavě předchozí šipky. Ukazuje se, že výsledný polygonální řetěz bude ve skutečnosti konvexní mnohoúhelník, který je Minkowského součtem P a Q.
jiný
Pokud je jeden polygon konvexní a jiný ne, složitost jejich Minkowského součtu je O (nm). Pokud jsou oba nekonvexní, jejich Minkowského součet je O ((mn)2).
Základní Minkowského součet
Existuje také pojem základní Minkowského součet +E dvou podmnožin euklidovského prostoru. Obvyklou Minkowského částku lze zapsat jako
To znamená, že základní Minkowského součet je definováno
kde μ označuje n-dimenzionální Lebesgueovo opatření. Důvodem pro výraz „základní“ je následující vlastnost funkce indikátorů: zatímco
je to vidět
kde "ess sup" označuje základní supremum.
Lp Minkowského součet
Pro K. a L kompaktní konvexní podmnožiny v , Minkowského součet lze popsat pomocí podpůrná funkce z konvexních sad:
Pro p ≥ 1, Firey[9] definoval Lp Minkowského součet K +pL kompaktních konvexních sad K. a L v obsahující původ jako
Podle Minkowského nerovnost, funkce hK +pL je opět pozitivní homogenní a konvexní, a proto podpůrná funkce kompaktní konvexní sady. Tato definice je zásadní v EU Lp Brunn-Minkowského teorie.
Viz také
- Blaschke součet
- Brunn – Minkowského věta, nerovnost na objemech Minkowksiho částek
- Konvoluce
- Dilatace
- Eroze
- Intervalová aritmetika
- Smíšený objem (aka Quermassintegral nebo vnitřní objem )
- Paralelní křivka
- Lemma Shapley – Folkman
- Topologický vektorový prostor # Vlastnosti
- Zonotop
Poznámky
- ^ Hadwiger, Hugo (1950), „Minkowskische Addition und Subtraktion beliebiger Punktmengen und die Theoreme von Erhard Schmidt“, Matematika. Z., 53 (3): 210–218, doi:10.1007 / BF01175656
- ^ Věta 3 (strany 562–563): Kerin, M.; Šmulian, V. (1940). "Na pravidelně konvexních množinách v prostoru konjugovaných s Banachovým prostorem". Annals of Mathematics. Druhá série. 41. str. 556–583. doi:10.2307/1968735. JSTOR 1968735. PAN 0002009.
- ^ Pro komutativitu Minkowského sčítání a konvexifikace, viz Věta 1.1.2 (strany 2–3) ve Schneiderovi; tento odkaz pojednává o velké části literatury o konvexní trupy Minkowského soupravy v jeho „kapitole 3 dodatku Minkowski“ (strany 126–196): Schneider, Rolf (1993). Konvexní tělesa: Brunn – Minkowského teorie. Encyklopedie matematiky a její aplikace. 44. Cambridge: Cambridge University Press. str. xiv + 490. ISBN 978-0-521-35220-8. PAN 1216521.
- ^ Kapitola 1: Schneider, Rolf (1993). Konvexní tělesa: Brunn – Minkowského teorie. Encyklopedie matematiky a její aplikace. 44. Cambridge: Cambridge University Press. str. xiv + 490. ISBN 978-0-521-35220-8. PAN 1216521.
- ^ Věta o Barbierovi (Java) v cut-the-uzel.
- ^ Kline, Jeffery (2019). "Vlastnosti problému d-dimenzionálního pohybu Země". Diskrétní aplikovaná matematika. 265: 128–141. doi:10.1016 / j.dam.2019.02.042.
- ^ Zelenyuk, V (2015). „Agregace účinnosti měřítka“. Evropský žurnál operačního výzkumu. 240 (1): 269–277. doi:10.1016 / j.ejor.2014.06.038.
- ^ Mayer, A .; Zelenyuk, V. (2014). „Agregace malmquistických indexů produktivity umožňující přerozdělení zdrojů“. Evropský žurnál operačního výzkumu. 238 (3): 774–785. doi:10.1016 / j.ejor.2014.04.003.
- ^ Firey, William J. (1962), "p- prostředky konvexních těl ", Matematika. Scand., 10: 17–24, doi:10,7146 / math.scand.a-10510
Reference
- Arrow, Kenneth J.; Hahn, Frank H. (1980). Obecná analýza konkurence. Pokročilé učebnice ekonomie. 12 (dotisk (1971) San Francisco, CA: Holden-Day, Inc. Mathematical economics texty.)6 vyd.). Amsterdam: Severní Holandsko. ISBN 978-0-444-85497-1. PAN 0439057.
- Gardner, Richard J. (2002), „Brunn-Minkowského nerovnost“, Býk. Amer. Matematika. Soc. (N.S.), 39 (3): 355–405 (elektronické), doi:10.1090 / S0273-0979-02-00941-2
- Zelená, Jerry; Heller, Walter P. (1981). "1 Matematická analýza a konvexita s aplikacemi v ekonomii". v Šipka, Kenneth Joseph; Intriligator, Michael D (eds.). Handbook of matematic economics, VolumeJá. Příručky v ekonomii. 1. Amsterdam: North-Holland Publishing Co. str. 15–52. doi:10.1016 / S1573-4382 (81) 01005-9. ISBN 978-0-444-86126-9. PAN 0634800.
- Henry Mann (1976), Věty o sčítání: Věty o sčítání teorie skupin a teorie čísel (Opravený dotisk 1965 Wiley ed.), Huntington, New York: Robert E. Krieger Publishing Company, ISBN 978-0-88275-418-5 - přes http://www.krieger-publishing.com/subcats/MathematicsandStatistics/mathematicsandstatistics.html
- Rockafellar, R. Tyrrell (1997). Konvexní analýza. Princetonské orientační body v matematice (Dotisk matematické řady Princeton z roku 197928 vyd.). Princeton, NJ: Princeton University Press. str. xviii + 451. ISBN 978-0-691-01586-6. PAN 1451876.
- Nathanson, Melvyn B. (1996), Teorie aditivních čísel: Inverzní problémy a geometrie sumersetů, GTM, 165Springer, Zbl 0859.11003.
- Oks, Eduard; Sharir, Micha (2006), „Minkowského součty monotónních a obecných jednoduchých polygonů“, Diskrétní a výpočetní geometrie, 35 (2): 223–240, doi:10.1007 / s00454-005-1206-r.
- Schneider, Rolf (1993), Konvexní tělesa: Brunn-Minkowského teorie, Cambridge: Cambridge University Press.
- Tao, Terence & Vu, Van (2006), Aditivní kombinatorika, Cambridge University Press.
- Mayer, A .; Zelenyuk, V. (2014). „Agregace malmquistických indexů produktivity umožňující přerozdělení zdrojů“. Evropský žurnál operačního výzkumu. 238 (3): 774–785. doi:10.1016 / j.ejor.2014.04.003.
- Zelenyuk, V (2015). „Agregace účinnosti měřítka“. Evropský žurnál operačního výzkumu. 240 (1): 269–277. doi:10.1016 / j.ejor.2014.06.038.
externí odkazy
- "Minkowski dodatek", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
- Howe, Rogere (1979), O tendenci k konvexitě vektorového součtu množin, Diskusní dokumenty nadace Cowles Foundation, 538, Cowles Foundation for Research in Economics, Univerzita Yale
- Minkowského součty, v Knihovna algoritmů výpočetní geometrie
- Minkowského součet dvou trojúhelníků a Minkowského součet disku a mnohoúhelníku George Beck, Demonstrační projekt Wolfram.
- Minkowského přidání konvexních tvarů podle Alexander Bogomolny: applet
- Wikibooks: OpenSCAD User Manual / Transformations # minkowski Marius Kintel: Aplikace