Otoczka wypukła

Przykład wielokąta wypukłego – otoczki wypukłej zbioru punktów

Otoczka wypukła, powłoka wypukła, uwypuklenie podzbioru przestrzeni liniowej – najmniejszy (w sensie inkluzji) zbiór wypukły zawierający ten podzbiór. Otoczkę wypukłą podzbioru $A$ oznacza się zwykle jako $\mathrm{conv}A.$

Przekrój dowolnej ilości zbiorów wypukłych jest zbiorem wypukłym, więc najmniejszy zbiór wypukły zawierający $A$ możemy zdefiniować jako przekrój wszystkich zbiorów wypukłych zawierających $A.$ Zapisujemy to za pomocą formuły:

$\mathrm{conv}A=\bigcap \{M:A\subset M\wedge M\text{jest wypukły}\}.$

Przykłady

• Powłoką wypukłą zbioru wypukłego jest ten sam zbiór. W szczególności zbiór pusty jest wypukły, zatem jego powłoką wypukłą jest zbiór pusty.
• Otoczką wypukłą zbioru dwupunktowego {A, B} jest odcinek AB.
• Powłoką wypukłą zbioru trzech punktów niewspółliniowych (takich, które nie leżą na wspólnej prostej) jest trójkąt o wierzchołkach w tych punktach.
• Dla dowolnego skończonego zbioru punktów płaszczyzny $\{P_1,P_2,\dots ,P_n\},$ gdzie $n>2$ powłoka wypukła tego zbioru jest wielokątem wypukłym (ewentualnie zdegenerowanym do odcinka) o wierzchołkach należących do zbioru $\{P_1,P_2,\dots ,P_n\}.$
  Analogicznie w przestrzeni 3-wymiarowej powłoka wypukła skończonego zbioru punktów jest wielościanem wypukłym (ewentualnie zdegenerowanym do wielokąta lub odcinka).
• W n-wymiarowej przestrzeni euklidesowej $E^n$ uwypukleniem zbioru punktów $(1,0,0,\dots ),(0,1,0,\dots ),\dots ,(0,\dots ,1)$ jest zbiór punktów o współrzędnych dodatnich, których suma jest równa 1. Zbiór taki nazywamy sympleksem. W przestrzeni 2-wymiarowej jest to odcinek, 3-wymiarowej trójkąt równoboczny, 4-wymiarowej czworościan foremny.

Alternatywne przedstawienie

Otoczkę wypukłą zbioru skończonego ($n$-elementowego) można scharakteryzować jako zbiór wszystkich wypukłych kombinacji liniowych elementów zbioru $A:$

$\mathrm{conv}A=\{x:x=\sum _{i=1}^n{\beta }_i{a}_i,\text{gdzie}{a}_i\in A,{\beta }_i\in {ℝ}_{+}\cup \{0\},\sum _{i=1}^n{\beta }_i=1,n\in \mathbb{N}\}$

Dowód

Oznaczmy operację tworzenia wszystkich wypukłych kombinacji liniowych elementów zbioru $A$ przez $f(A).$ Udowodnimy, że: $(*)\mathrm{conv}A=f(A).$ Zauważmy, że $A\subseteq f(A)$ (wystarczy wziąć w definicji $n=1$ i ${\beta }_1=1$).

Wykażemy teraz, że $f(A)$ jest zbiorem wypukłym: niech $x,y\in f(A).$ Zatem dla pewnych $a_1,\dots ,a_n,b_1,\dots ,b_m\in A$ oraz dodatnich ${\alpha }_1,\dots ,{\alpha }_n,{\beta }_1,\dots ,{\beta }_m$ mamy

$x=\sum _{i=1}^n{\alpha }_i{a}_i,$ $y=\sum _{i=1}^m{\beta }_i{b}_i$ oraz ${\alpha }_1+\dots +{\alpha }_n=1={\beta }_1+\dots +{\beta }_m.$

Niech $\alpha ,\beta ⩾0$ będą takie, że $\alpha +\beta =1.$ Wówczas

$1=\alpha \sum _{i=1}^n{\alpha }_i+\beta \sum _{i=1}^m{\beta }_i=\sum _{i=1}^n(\alpha {\alpha }_i)+\sum _{i=1}^m(\beta {\beta }_i)$

i stąd

$\alpha x+\beta y=\sum _{i=1}^n(\alpha {\alpha }_i)a_i+\sum _{i=1}^m(\beta {\beta }_i)b_i\in f(A).$

Aby wykazać równość zbiorów postulowaną w $(*)$ udowodnimy dwie inkluzje. Najpierw:

$\mathrm{conv}A=\bigcap \{M:A\subset M\text{gdzie}M-\text{wypukły}\}\subset f(A)$

Inkluzja zachodzi ponieważ w szczególności jednym ze zbiorów M zawierających zbiór A jest $f(A)$ zatem cześć wspólna wszystkich zbiorów wypukłych zawierających A musi się zawierać w $f(A).$ Zatem $\mathrm{conv}A\subset f(A).$

Teraz inkluzja w drugą stronę:

Przypuśćmy, że M jest zbiorem wypukłym takim, że $A\subseteq M.$ Teraz z obu stron inkluzji wykonujemy operację $f$ otrzymując:

$f(A)\subset f(M)=M,$

Ponieważ tak jest dla każdego zbioru M więc także dla części wspólnej wszystkich zbiorów wypukłych M zawierających A zatem:

$f(A)\subset \bigcap \{M:A\subset M,M-\text{wypukły}\}=\mathrm{conv}A,$

Stąd $f(A)\subset \mathrm{conv}A,$ a więc $f(A)=\mathrm{conv}A.$

Zobacz też

• algorytm Grahama
• algorytm Jarvisa
• quickhull