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

Из Википедије, слободне енциклопедије
Црвена фигура је збир плаве и зелене фигуре.

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

A + B = \{\mathbf{a}+\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.

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

A - B = \{\mathbf{a}-\mathbf{b}\,|\,\mathbf{a}\in A,\ \mathbf{b}\in B\}.
збир Минковског A + B
B
A

Пример[уреди]

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

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

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.
У конвексном омотачу црвеног скупа свака плава тачка је конвексна комбинација неких црвених тачака.
Three squares are shown in the non-negative quadrant of the Cartesian plane. The square Q1=Шаблон:Closed-closed×Шаблон:Closed-closed is green. The square Q2=Шаблон:Closed-closed×Шаблон:Closed-closed is brown, and it sits inside the turquoise square Q1+Q2=Шаблон:Closed-closed×Шаблон:Closed-closed.
Сабирање Минковског скупова. Збир квадрата 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]

Ако је Шаблон:Mvar конвексни скуп \mu S+\lambda S је конвексни сет; онда

\mu S+\lambda S=(\mu+\lambda)S за сваки \mu,\lambda \geq 0.

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

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

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

Примене[уреди]

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

Планирање кретања[уреди]

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

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

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

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

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

Пример у равни[уреди]

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

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

Oстало[уреди]

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

Основни збир Минковског[уреди]

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

A + B = \{ z \in \mathbb{R}^{n} \,|\, A \cap (\{z\} - B) \neq \emptyset \}.

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

A +_{\mathrm{e}} B = \{ z \in \mathbb{R}^{n} \,|\, \mu \left[A \cap (\{z\} - B)\right] > 0 \},

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

1_{A \,+\, B} (z) = \sup_{x \,\in\, \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),

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

1_{A \,+_{\mathrm{e}}\, B} (z) = \mathop{\mathrm{ess\,sup}}_{x \,\in\, \mathbb{R}^{n}} 1_{A} (x) 1_{B} (z - x),

где "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: pp. 556–583. DOI:10.2307/1968735. JSTOR 1968735. MR 2009. 
  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 0-521-35220-7. MR 1216521. 
  3. ^ The Theorem of Barbier (Java) at cut-the-knot.

Референце[уреди]

Шаблон:Functional Analysis