Otoczka wypukła

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 ${\displaystyle A}$ oznacza się zwykle jako ${\displaystyle \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 ${\displaystyle A}$ możemy zdefiniować jako przekrój wszystkich zbiorów wypukłych zawierających ${\displaystyle A.}$ Zapisujemy to za pomocą formuły:

${\displaystyle \operatorname {conv} A=\bigcap \{M:A\subset M\;\land \;M~~{\mbox{jest wypukły}}\}.}$

• 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 ${\displaystyle \{P_{1},P_{2},\dots ,P_{n}\},}$ gdzie ${\displaystyle n>2}$ powłoka wypukła tego zbioru jest wielokątem wypukłym (ewentualnie zdegenerowanym do odcinka) o wierzchołkach należących do zbioru ${\displaystyle \{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 ${\displaystyle E^{n}}$ uwypukleniem zbioru punktów ${\displaystyle (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.

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

${\displaystyle \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\}}$

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

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

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

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

${\displaystyle 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

${\displaystyle \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 ${\displaystyle (*)}$ udowodnimy dwie inkluzje. Najpierw:

${\displaystyle \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 ${\displaystyle f(A)}$ zatem cześć wspólna wszystkich zbiorów wypukłych zawierających A musi się zawierać w ${\displaystyle f(A).}$ Zatem ${\displaystyle \operatorname {conv} A\subset f(A).}$

Teraz inkluzja w drugą stronę:

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

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

${\displaystyle f(A)\subset \bigcap \{M:A\subset M,M-{\mbox{wypukły}}\}=\operatorname {conv} A,}$

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

• algorytm Grahama
• algorytm Jarvisa
• quickhull