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

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{:}$

$\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},\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}+\ldots +\alpha _{n}=1=\beta _{1}+\ldots +\beta _{m}.$

Niech $\alpha ,\beta \geqslant 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{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 $\operatorname {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-{\mbox{wypukły}}\}=\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