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

Извор: testwiki
Пређи на навигацију Пређи на претрагу
Црвена фигура је збир плаве и зелене фигуре.

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

A+B={𝐚+𝐛|𝐚∈A, 𝐛∈B}.

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

A−B={𝐚−𝐛|𝐚∈A, 𝐛∈B}.
збир Минковског Шаблон:Math
B
A

Пример

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

Шаблон:Math

и

Шаблон:Math,

онда је збир Минковског Шаблон:Math, што изгледа као шестоугао, са три 'поновљене' тачке Шаблон:Math.

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

S + {0} = S;

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

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 конвексни скуп μS+λS је конвексни сет; онда

μS+λS=(μ+λ)S за сваки μ,λ≥0.

Обрнуто, ако ова „дистрибутивна карактеристика" важи за све реалне бројеве који нису негативни, μ,λ, онда је скуп конвексан.[3] Фигура приказује пример неконвексног скупа за који је Шаблон:Math.

Пример неконвексног скупа тако да је Шаблон:Math

Суме Минковског се понашају линеарно на спољној линији дводимензионалних конвексних тела: спољна линија тог збира једнака је збиру спољнјих линија. Уз то, ако је 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 два подскупа Еуклидовог простора. Уобичајени збир Минковског се може забележити као

A+B={z∈ℝn|A∩({z}−B)≠∅}.

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

A+eB={z∈ℝn|μ[A∩({z}−B)]>0},

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

1A+B(z)=supx∈ℝn1A(x)1B(z−x),

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

1A+eB(z)=esssupx∈ℝn1A(x)1B(z−x),

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

Референце

Шаблон:Reflist

Литература

Шаблон:Functional Analysis

Шаблон:Нормативна контрола

  1. ↑ Theorem 3 (pages 562–563): Шаблон:Cite news
  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): Шаблон:Cite book
  3. ↑ Chapter 1: Шаблон:Cite book
  4. ↑ The Theorem of Barbier (Java) at cut-the-knot.
Преузето из „https://sr.wiki.beta.math.wmflabs.org/w/index.php?title=Сабирање_Минковског&oldid=6392”