Сабирање Минковског

У геометрији збир Минковског (такође познат као дилација) два скупа позиционих вектора А и В у Еуклидовом простору формира се додавањем сваког вектора у А сваком вектору у В тј скуп

Црвена фигура је збир плаве и зелене фигуре.

Аналогно, разлика Минковског дефинише се на следећи начин

збир Минковског A + B
B
A

ПримерУреди

На пример, ако имамо два скупа А и В, при чему се сваки од њих састоји из три позициона вектора (неформално речено, три тачке), који представљају углове два троуглова у  , са координатама

A = {(1, 0), (0, 1), (0, −1)} 

и

B = {(0, 0), (1, 1), (1, −1)} ,

онда је збир Минковског A + B = {(1, 0), (2, 1), (2, −1), (0, 1), (1, 2), (1, 0), (0, −1), (1, 0), (1, −2)} , што изгледа као шестоугао, са три 'поновљене' тачке (1, 0).

За збир Минковског, нулти скуп;{0}, који садржи само нулти вектор 0, представља неутрални елемент: за сваки подскуп S векторског простора

S + {0} = S;

Празан скуп је важан код сабирања Минковског зато што сваки празан скуп поништава сваки други подскуп - за сваки други подскуп S, векторског простора, његов збир са празним скупом је празан: S +   =  .

 
У конвексном омотачу црвеног скупа свака плава тачка је конвексна комбинација неких црвених тачака.
 
Сабирање Минковског скупова. Збир квадрата Q1=Шаблон:Closed-closed2 и Q2=Шаблон:Closed-closed2 је квадрат  Q1+Q2=Шаблон:Closed-closed2.

Конвексни омотачи збира МинковскогУреди

Сабирање Минковског понаша се добро у случају поступка узимања конвексних омотача што је приказано у следећој тврдњи:

  • За све подскупове S1 и S2 реалног векторског простора, конвексни омотач њихових збирова представља збир њихових конвексних омотача
Conv(S1 + S2) = Conv(S1) + Conv(S2).

Овај резултат важи уопштење за сваки коначни низ скупова који нису празни

Conv(∑Sn) = ∑Conv(Sn).

У математичкој терминологији, операције сабирања Минковског и формирања конвексних омотача представљају операције замене.[1][2]

Ако је S конвексни скуп   је конвексни сет; онда

  за сваки  .

Обрнуто, ако ова „дистрибутивна карактеристика" важи за све реалне бројеве који нису негативни,  , онда је скуп конвексан.[3] Фигура приказује пример неконвексног скупа за који је A + A ≠ 2A.

 
Пример неконвексног скупа тако да је A + A ≠ 2A

Суме Минковског се понашају линеарно на спољној линији дводимензионалних конвексних тела: спољна линија тог збира једнака је збиру спољнјих линија. Уз то, ако је K (унутрашњост) крива константне ширине, онда је збир K и његове ротације за 180 степени диск. Ове 2 чињенице могу се комбиновати и дати кратак доказ Барбијеве теореме о спољним линијама константне сфере.[4]

ПрименеУреди

Сабирање Минковског игра средишњу улогу у математичкој морфологији. Оно се појављује код парадигме потеза 2D компјутерске графике (са разним применама, нарочито код Доналда Е.Кната у Мегафонту), као и код операције померања тачака код чврстог тела код 3D компјутерске графике.

Планирање кретањаУреди

Збирови Минковског користе се код планирања кретања предмета између препрека. Користе се за рачунање конфигурационих простора, који представљају скуп присутних позиција предмета. Код просторног модела транслационог кретања једног предмета у авиону, где позиција предмета може бити јединствено дефинисана позицијом једне фиксне тачке овог предмета, конфигурациони простор представљаја збир Минковског скупа препрека и покретног предмета постављеног на почетку и ротираног за 180 степени.

Нумеричка контрола (NC) рада машинаУреди

Код нумеричке контроле рада машина, програмирање NC алатке базира се на чињеници да збир Минковског алатке за сечење са њеном путањом даје облик исечку у материјалу.

Алгоритми за рачунање Минковсковог збираУреди

 
Сабирање Минковског и конвексни омотачи. 16 тамноцрвених тачака (десно) формирају збир Минковског 4 неконвексна скупа (лево), од којих се сваки састоји од пара црвених тачака. Њихови конвексни омотачи (осенчени розе бојом) садрже знаке плус (+): Десни знак плус једнак је збиру левих знакова плус.

Пример у равниУреди

Два конвексна многоугла у равниУреди

За два конвексна многоугла P и Q у равни са угловима m и n, њихов збир је једнак је конвексном многоуглу са највише m + n угловима и може се израчунати у времену O (m + n) веома једноставним поступком, Претпоставимо да су дате ивице многоугла. Претпоставимо да су дате ивице многоугла, а смер је нпр. у смеру казаљке на сату дуж границе многоугла. Онда се лако види да ове ивице конвексног многоугла одређује угао дводимензионалног координатног система. Хајде сад да убацимо одређене распореде усмерених ивица из P и Q у један одређени распоред S. Замислимо да су те ивице чврсте стрелице које се могу слободно кретари док истовремено иду паралелно свом првобитном правцу. Склопимо те стрелице у ред редоследа S везујући крај следеће стрелицеза почетак претходне. Произилази да ће резултујући многоугаони ланац у ствари бити конвексни многоугао који је збир Минковског P и Q.

ОсталоУреди

Ако је један многоугао конвексан, а други није, комплексност њиховог збира Минковског је O(nm). Ако су оба неконвексна, комплексност њиховог збира је O((mn)2).

Основни збир МинковскогУреди

Постоји такође и појам основног збира Минковског +e два подскупа Еуклидовог простора. Уобичајени збир Минковског се може забележити као

 

Тако се основни збир Минковског дефинише овако

 

где μ означава n-димензионалну Лебескову меру. Разлог за термин "основни" леђи у следећој одлици индикаторске функције: док је

 

може се видети као

 

где "ess sup" означава основни супремум.

РеференцеУреди

  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. стр. 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. стр. 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. стр. xiv+490. ISBN 978-0-521-35220-8. MR 1216521. 
  4. ^ The Theorem of Barbier (Java) at cut-the-knot.

ЛитератураУреди

Шаблон:Functional Analysis