Sabiranje Minkovskog

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

Crvena figura je zbir plave i zelene figure.

Analogno, razlika Minkovskog definiše se na sledeći način

zbir Minkovskog A + B
B
A

Primer uredi

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 +   =  .

 
U konveksnom omotaču crvenog skupa svaka plava tačka je konveksna kombinacija nekih crvenih tačaka.
 
Sabiranje Minkovskog skupova. Zbir kvadrata Q1=[0,1]2Q2=[1,2]2 je kvadrat  Q1+Q2=[1,3]2.

Konveksni omotači zbira Minkovskog uredi

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.

 
Primer nekonveksnog skupa tako da je A + A ≠ 2A

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

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

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

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

 
Sabiranje Minkovskog i konveksni omotači. 16 tamnocrvenih tačaka (desno) formiraju zbir Minkovskog 4 nekonveksna skupa (levo), od kojih se svaki sastoji od para crvenih tačaka. Njihovi konveksni omotači (osenčeni roze bojom) sadrže znake plus (+): Desni znak plus jednak je zbiru levih znakova plus.

Primer u ravni uredi

Dva konveksna mnogougla u ravni uredi

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

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

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

  1. ^ 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. 
  2. ^ 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. 
  3. ^ 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. 
  4. ^ The Theorem of Barbier (Java) at cut-the-knot.

Literatura uredi

Šablon:Functional Analysis