Пређи на садржај

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

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

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

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

збир Минковског 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 + = .

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=[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].
Сабирање Минковског скупова. Збир квадрата Q1=[0,1]2 и Q2=[1,2]2 је квадрат  Q1+Q2=[1,3]2.

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

[уреди | уреди извор]

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

  • За све подскупове 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 алатке базира се на чињеници да збир Минковског алатке за сечење са њеном путањом даје облик исечку у материјалу.

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

[уреди | уреди извор]
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(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