Sabiranje Minkovskog
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/10/%D0%A1%D1%83%D0%BC%D0%BC%D0%B0_%D0%9C%D0%B8%D0%BD%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%BE%D0%B3%D0%BE.svg/220px-%D0%A1%D1%83%D0%BC%D0%BC%D0%B0_%D0%9C%D0%B8%D0%BD%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%BE%D0%B3%D0%BE.svg.png)
U geometriji zbir Minkovskog (takođe poznat kao dilacija) dva skupa pozicionih vektora A i V u Euklidovom prostoru formira se dodavanjem svakog vektora u A svakom vektoru u V tj skup
Analogno, razlika Minkovskog definiše se na sledeći način
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Minkowski-sumex4.svg/220px-Minkowski-sumex4.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Minkowski-sumex2.svg/220px-Minkowski-sumex2.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Minkowski-sumex1.svg/220px-Minkowski-sumex1.svg.png)
Primer[uredi | uredi izvor]
Na primer, ako imamo dva skupa A i V, pri čemu se svaki od njih sastoji iz tri poziciona vektora (neformalno rečeno, tri tačke), koji predstavljaju uglove dva trouglova u , sa koordinatama
- A = {(1, 0), (0, 1), (0, −1)}
i
- B = {(0, 0), (1, 1), (1, −1)} ,
onda je zbir Minkovskog A + B = {(1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)} , što izgleda kao šestougao, sa tri 'ponovljene' tačke (1, 0).
Za zbir Minkovskog, nulti skup;{0}, koji sadrži samo nulti vektor 0, predstavlja neutralni element: za svaki podskup S vektorskog prostora
- S + {0} = S;
Prazan skup je važan kod sabiranja Minkovskog zato što svaki prazan skup poništava svaki drugi podskup - za svaki drugi podskup S, vektorskog prostora, njegov zbir sa praznim skupom je prazan: S + = .
![A picture of a smoothed triangle, like a triangular tortilla-chip or a triangular road-sign. Each of the three rounded corners is drawn with a red curve. The remaining interior points of the triangular shape are shaded with blue.](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8e/Extreme_points.svg/220px-Extreme_points.svg.png)
![Three squares are shown in the non-negative quadrant of the Cartesian plane. The square Q1=[0,1]×[0,1] is green. The square Q2=[1,2]×[1,2] is brown, and it sits inside the turquoise square Q1+Q2=[1,3]×[1,3].](http://upload.wikimedia.org/wikipedia/commons/thumb/d/de/Minkowski_sum.png/220px-Minkowski_sum.png)
Konveksni omotači zbira Minkovskog[uredi | uredi izvor]
Sabiranje Minkovskog ponaša se dobro u slučaju postupka uzimanja konveksnih omotača što je prikazano u sledećoj tvrdnji:
- Za sve podskupove S1 i S2 realnog vektorskog prostora, konveksni omotač njihovih zbirova predstavlja zbir njihovih konveksnih omotača
- Conv(S1 + S2) = Conv(S1) + Conv(S2).
Ovaj rezultat važi uopštenje za svaki konačni niz skupova koji nisu prazni
- Conv(∑Sn) = ∑Conv(Sn).
U matematičkoj terminologiji, operacije sabiranja Minkovskog i formiranja konveksnih omotača predstavljaju operacije zamene.[1][2]
Ako je S konveksni skup je konveksni set; onda
- za svaki .
Obrnuto, ako ova „distributivna karakteristika" važi za sve realne brojeve koji nisu negativni, , onda je skup konveksan.[3] Figura prikazuje primer nekonveksnog skupa za koji je A + A ≠ 2A.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/62/Minkowskisum.svg/220px-Minkowskisum.svg.png)
Sume Minkovskog se ponašaju linearno na spoljnoj liniji dvodimenzionalnih konveksnih tela: spoljna linija tog zbira jednaka je zbiru spoljnjih linija. Uz to, ako je K (unutrašnjost) kriva konstantne širine, onda je zbir K i njegove rotacije za 180 stepeni disk. Ove 2 činjenice mogu se kombinovati i dati kratak dokaz Barbijeve teoreme o spoljnim linijama konstantne sfere.[4]
Primene[uredi | uredi izvor]
Sabiranje Minkovskog igra središnju ulogu u matematičkoj morfologiji. Ono se pojavljuje kod paradigme poteza 2D kompjuterske grafike (sa raznim primenama, naročito kod Donalda E.Knata u Megafontu), kao i kod operacije pomeranja tačaka kod čvrstog tela kod 3D kompjuterske grafike.
Planiranje kretanja[uredi | uredi izvor]
Zbirovi Minkovskog koriste se kod planiranja kretanja predmeta između prepreka. Koriste se za računanje konfiguracionih prostora, koji predstavljaju skup prisutnih pozicija predmeta. Kod prostornog modela translacionog kretanja jednog predmeta u avionu, gde pozicija predmeta može biti jedinstveno definisana pozicijom jedne fiksne tačke ovog predmeta, konfiguracioni prostor predstavljaja zbir Minkovskog skupa prepreka i pokretnog predmeta postavljenog na početku i rotiranog za 180 stepeni.
Numerička kontrola (NC) rada mašina[uredi | uredi izvor]
Kod numeričke kontrole rada mašina, programiranje NC alatke bazira se na činjenici da zbir Minkovskog alatke za sečenje sa njenom putanjom daje oblik isečku u materijalu.
Algoritmi za računanje Minkovskovog zbira[uredi | uredi izvor]
![Minkowski addition of four line-segments. The left-hand pane displays four sets, which are displayed in a two-by-two array. Each of the sets contains exactly two points, which are displayed in red. In each set, the two points are joined by a pink line-segment, which is the convex hull of the original set. Each set has exactly one point that is indicated with a plus-symbol. In the top row of the two-by-two array, the plus-symbol lies in the interior of the line segment; in the bottom row, the plus-symbol coincides with one of the red-points. This completes the description of the left-hand pane of the diagram. The right-hand pane displays the Minkowski sum of the sets, which is the union of the sums having exactly one point from each summand-set; for the displayed sets, the sixteen sums are distinct points, which are displayed in red: The right-hand red sum-points are the sums of the left-hand red summand-points. The convex hull of the sixteen red-points is shaded in pink. In the pink interior of the right-hand sumset lies exactly one plus-symbol, which is the (unique) sum of the plus-symbols from the right-hand side. The right-hand plus-symbol is indeed the sum of the four plus-symbols from the left-hand sets, precisely two points from the original non-convex summand-sets and two points from the convex hulls of the remaining summand-sets.](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Shapley%E2%80%93Folkman_lemma.svg/300px-Shapley%E2%80%93Folkman_lemma.svg.png)
Primer u ravni[uredi | uredi izvor]
Dva konveksna mnogougla u ravni[uredi | uredi izvor]
Za dva konveksna mnogougla P i Q u ravni sa uglovima m i n, njihov zbir je jednak je konveksnom mnogouglu sa najviše m + n uglovima i može se izračunati u vremenu O (m + n) veoma jednostavnim postupkom, Pretpostavimo da su date ivice mnogougla. Pretpostavimo da su date ivice mnogougla, a smer je npr. u smeru kazaljke na satu duž granice mnogougla. Onda se lako vidi da ove ivice konveksnog mnogougla određuje ugao dvodimenzionalnog koordinatnog sistema. Hajde sad da ubacimo određene rasporede usmerenih ivica iz P i Q u jedan određeni raspored S. Zamislimo da su te ivice čvrste strelice koje se mogu slobodno kretari dok istovremeno idu paralelno svom prvobitnom pravcu. Sklopimo te strelice u red redosleda S vezujući kraj sledeće streliceza početak prethodne. Proizilazi da će rezultujući mnogougaoni lanac u stvari biti konveksni mnogougao koji je zbir Minkovskog P i Q.
Ostalo[uredi | uredi izvor]
Ako je jedan mnogougao konveksan, a drugi nije, kompleksnost njihovog zbira Minkovskog je O(nm). Ako su oba nekonveksna, kompleksnost njihovog zbira je O((mn)2).
Osnovni zbir Minkovskog[uredi | uredi izvor]
Postoji takođe i pojam osnovnog zbira Minkovskog +e dva podskupa Euklidovog prostora. Uobičajeni zbir Minkovskog se može zabeležiti kao
Tako se osnovni zbir Minkovskog definiše ovako
gde μ označava n-dimenzionalnu Lebeskovu meru. Razlog za termin "osnovni" leđi u sledećoj odlici indikatorske funkcije: dok je
može se videti kao
gde "ess sup" označava osnovni supremum.
Reference[uredi | uredi izvor]
- ^ Theorem 3 (pages 562–563): Krein, M.; Šmulian, V. (1940). „On regularly convex sets in the space conjugate to a Banach space”. Annals of Mathematics (2), Second series. 41. str. 556—583. JSTOR 1968735. MR 2009. doi:10.2307/1968735.
- ^ For the commutativity of Minkowski addition and convexification, see Theorem 1.1.2 (pages 2–3) in Schneider; this reference discusses much of the literature on the convex hulls of Minkowski sumsets in its "Chapter 3 Minkowski addition" (pages 126–196): Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of mathematics and its applications. 44. Cambridge: Cambridge University Press. str. xiv+490. ISBN 978-0-521-35220-8. MR 1216521.
- ^ Chapter 1: Schneider, Rolf (1993). Convex bodies: The Brunn–Minkowski theory. Encyclopedia of mathematics and its applications. 44. Cambridge: Cambridge University Press. str. xiv+490. ISBN 978-0-521-35220-8. MR 1216521.
- ^ The Theorem of Barbier (Java) at cut-the-knot.
Literatura[uredi | uredi izvor]
- Arrow, Kenneth J.; Hahn, Frank H. (1980). General competitive analysis. Advanced textbooks in economics. 12 (reprint of (1971) San Francisco, CA: Holden-Day, Inc. Mathematical economics texts. 6 izd.). Amsterdam: North-Holland. ISBN 978-0-444-85497-1. MR 439057.
- Gardner, Richard J. (2002), „The Brunn-Minkowski inequality”, Bull. Amer. Math. Soc. (N.S.), 39 (3): 355—405 (electronic), doi:10.1090/S0273-0979-02-00941-2
- Green, Jerry; Heller, Walter P. (1981). „1 Mathematical analysis and convexity with applications to economics”. Ur.: Arrow, Kenneth Joseph; Intriligator, Michael D. Handbook of mathematical economics, Volume I. Handbooks in economics. 1. Amsterdam: North-Holland Publishing Co. str. 15—52. ISBN 978-0-444-86126-9. MR 634800. doi:10.1016/S1573-4382(81)01005-9. Arhivirano iz originala 17. 12. 2012. g. Pristupljeno 15. 05. 2014.
- Mann, Henry (1976), Addition Theorems: The Addition Theorems of Group Theory and Number Theory (Corrected reprint of 1965 Wiley izd.), Huntington, New York: Robert E. Krieger Publishing Company, ISBN 978-0-88275-418-5 Spoljašnja veza u
|publisher=
(pomoć) - Rockafellar, R. Tyrrell (1997). Convex analysis. Princeton landmarks in mathematics (Reprint of the 1979 Princeton mathematical series 28 izd.). Princeton, NJ: Princeton University Press. str. xviii+451. ISBN 978-0-691-01586-6. MR 1451876. MR274683.
- Nathanson, Melvyn B. (1996), Additive Number Theory: Inverse Problems and Geometry of Sumsets, GTM, 165, Springer, Zbl 0859.11003.
- Oks, Eduard; Sharir, Micha (2006), „Minkowski Sums of Monotone and General Simple Polygons”, Discrete and Computational Geometry, 35 (2): 223—240, doi:10.1007/s00454-005-1206-y.
- Schneider, Rolf (1993), Convex bodies: the Brunn-Minkowski theory, Cambridge: Cambridge University Press.
- Tao, Terence & Vu, Van (2006), Additive Combinatorics, Cambridge University Press.