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$$A$ oznacza się zwykle jako $\operatorname {conv} A.$$\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\;\land \;M~~{\mbox{jest wypukły}}\}.$$\operatorname {conv} A=\bigcap \{M:A\subset M\;\land \;M~~{\mbox{jest wypukły}}\}.$

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\;$$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}\}$$\{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}\;$$E^{n}\;$ uwypukleniem zbioru punktów $(1,0,0,\dots ),(0,1,0,\dots ),\dots ,(0,\dots ,1)$$(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$$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\}$$\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$$A$ przez $f(A)$$f(A)$. Udowodnimy, że :$(*)\qquad \operatorname {conv} A=f(A)$$(*)\qquad \operatorname {conv} A=f(A)$. Zauważmy, że $A\subseteq f(A)$$A\subseteq f(A)$ (wystarczy wziąć w definicji $n=1\,$$n=1\,$ i $\beta _{1}=1\,$$\beta _{1}=1\,$).

Wykażemy teraz, że $f(A)$$f(A)$ jest zbiorem wypukłym: niech $x,y\in f(A)$$x,y\in f(A)$. Zatem, dla pewnych $a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in A$$a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in A$ oraz dodatnich $\alpha _{1},\ldots ,\alpha _{n},\beta _{1},\ldots ,\beta _{m}$$\alpha _{1},\ldots ,\alpha _{n},\beta _{1},\ldots ,\beta _{m}$ mamy

$x=\sum _{i=1}^{n}\alpha _{i}a_{i}$$x=\sum _{i=1}^{n}\alpha _{i}a_{i}$, $y=\sum _{i=1}^{m}\beta _{i}b_{i}$$y=\sum _{i=1}^{m}\beta _{i}b_{i}$ oraz $\alpha _{1}+\ldots +\alpha _{n}=1=\beta _{1}+\ldots +\beta _{m}$$\alpha _{1}+\ldots +\alpha _{n}=1=\beta _{1}+\ldots +\beta _{m}$.

Niech $\alpha ,\beta \geq 0$$\alpha ,\beta \geq 0$ będą takie, że $\alpha +\beta =1$$\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})$$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)$$\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{wypukły}}\}\subset f(A)$$\operatorname {conv} A=\bigcap \{M:A\subset M\;{\mbox{gdzie}}\;M-{\mbox{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)$$f(A)$ zatem cześć wspólna wszystkich zbiorów wypukłych zawierających A musi się zawierać w $f(A)$$f(A)$. Zatem $\operatorname {conv} A\subset f(A)$$\operatorname {conv} A\subset f(A)$.

Teraz inkluzja w druga stronę:

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

$f(A)\subset f(M)=M$$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-{\mbox{wypukły}}\}=\operatorname {conv} A$$f(A)\subset \bigcap \{M:A\subset M,M-{\mbox{wypukły}}\}=\operatorname {conv} A$

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

Zobacz też

• algorytm Grahama
• algorytm Jarvisa
• quickhull