Wypukła otoczka

Z Wikipedii

Wypukła otoczka (powłoka wypukła, uwypuklenie) zbioru $A$ będącego podzbiorem przestrzeni liniowej jest to najmniejszy (w sensie inkluzji) zbiór wypukły zawierający $A$ . Otoczkę wypukłą $A$ oznacza się zwykle jako: $\operatorname{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:

$\operatorname{conv} A = \bigcap\{M: A\subset M \; \mbox{oraz} \; M - \mbox{wypukly} \}.$

Spis treści

1 Przykłady
2 Alternatywne przedstawienie
- 2.1 Dowód
3 Zobacz też

[edytuj] Przykłady

Powłoką wypukłą zbioru wypukłego jest ten sam zbiór.
Dla dowolnego skończonego zbioru punktów płaszczyzny {P₁, P₂, ..., 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,..., 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).
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.
Otoczką wypukłą zbioru dwupunktowego {A, B} jest odcinek AB.
W n-wymiarowej przestrzeni eukldesowej $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.

[edytuj] Alternatywne przedstawienie

Otoczkę wypukłą można scharakteryzować jako zbiór wszystkich wypukłych kombinacji liniowych elementów zbioru $A$ :

$\operatorname{conv} A = \left\{ x : \; x=\sum_{i=1}^{n}\beta_i a_i, \;\;\; \mbox{gdzie} \;\;\; a_i\in A, \;\; \beta_i \in\mathbb{R}_{+}\cup\{0\}, \;\sum_{i=1}^{n}\beta_i = 1, \; n\in\mathbb{N} \right\}$

[edytuj] Dowód

Oznaczmy operację tworzenia wszystkich wypukłych kombinacji liniowych elementów zbioru $A$ przez $f (A)$ . Udowodnimy, że : $(*)\qquad\operatorname{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,\ldots,a_n,b_1,\ldots,b_m \in A$ oraz dodatnich $\alpha_1,\ldots,\alpha_n,\beta_1,\ldots,\beta_m$ mamy

$x=\sum_{i=1}^{n}\alpha_i a_i$ , $y=\sum_{i=1}^{m}\beta_i b_i$ oraz $\alpha_1+\ldots+\alpha_n=1=\beta_1+\ldots+\beta_m$ .

Niech $\alpha,\beta\geq 0$ będą takie, że $α + β = 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:

$\operatorname{conv} A = \bigcap\{M : A \subset M \; \mbox{gdzie} \; M-\mbox{wypukly}\} \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 $\operatorname{conv} A \subset f(A)$ .