Otoczka wypukła

Otoczka wypukła, powłoka wypukła 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 $\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 \; \and\; M~~ \mbox{jest wypukly} \}.$

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 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łą 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\}$

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 $\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:

$\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)$.

Teraz inkluzja w druga 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 wiec 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-\mbox{wypukly} \} = \operatorname{conv} A$

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

Zobacz też

• algorytm Grahama
• algorytm Jarvisa
• quickhull