Konvexní obal

Konvexní trup množiny je nejmenší konvexní množina obsahující . "Nejmenší množina" zde znamená nejmenší prvek s ohledem na vložení množin, tj. konvexní množinu obsahující daný obrazec tak, že je obsažena v jakékoli jiné konvexní sadě obsahující daný obrazec. $X$ $X$

Typicky je konvexní trup definován pro podmnožiny vektorového prostoru nad reals (zejména v euklidovském prostoru ) a na odpovídajících afinních prostorech .

Konvexní trup sady je obvykle označen . $X$ $\operatorname {Conv}X$

Příklad

Představte si prkno, do kterého je zatlučeno mnoho hřebíků – ale ne do samotné hlavy. Vezměte lano, navažte na něj posuvnou smyčku ( laso ) a hoďte ji na prkno a poté utáhněte. Lano obepíná všechny hřeby, ale dotýká se jen některých krajních. V této poloze je smyčka a oblast desky, kterou obklopuje, konvexní skořepina pro celou skupinu hřebíků [1] .

Vlastnosti

$X$ je konvexní množina tehdy a jen tehdy, když . $\operatorname {Conv} X=X$
Pro libovolnou podmnožinu lineárního prostoru existuje jedinečný konvexní obal - to je průnik všech konvexních množin obsahujících . $X$ $\operatorname {Conv}X$ $X$
- V čem $\operatorname {Conv}X=\bigcup _{{n=1}}^({\infty }}~\bigcup _{{a_{1},\tečky ,a_{n}\in X}}~\bigcup _{{\lambda _{1}+\tečky +\lambda _{n}=1)){\lambda _{1}a_{1}+\tečky +\lambda _{n}a_{n)), ~\lambda _{i}\geq 0$
- Navíc, pokud je rozměr prostoru stejný , platí následující Carathéodoryho věta : $N$ $\operatorname {Conv}X=\bigcup _{{a_{1},\tečky ,a_{{N+1}}\in X}}\bigcup _{{\lambda _{1}+\tečky +\lambda _{{N+1}}=1}}{\lambda _{1}a_{1}+\tečky +\lambda _{{N+1}}a_{{N+1}}},~\lambda _{i}\geq 0$
Konvexní obal konečné množiny bodů v rovině je konvexní plochý mnohoúhelník (v degenerovaných případech segment nebo bod) a jeho vrcholy jsou podmnožinou původní množiny bodů. Podobná skutečnost platí pro konečnou množinu bodů ve vícerozměrném prostoru.
Konvexní obal je roven průniku všech poloprostorů obsahujících . $X$ $X$
Krein-Milmanova věta . Konvexní kompakt v lokálně konvexním prostoru se shoduje s uzavřením konvexního trupu množiny jeho krajních bodů $K$ $L$ $E(K)$

Variace a zobecnění

Konvexní obal funkce f je funkce taková, že $\operatorname {Conv}f$

\operatorname {epi}\;\operatorname {Conv}f=\operatorname {Conv}\;\operatorname {epi}f

kde epi f je epigraf funkce f .

Za povšimnutí stojí souvislost mezi konceptem konvexního obalu funkce a Legendreovou transformací nekonvexních funkcí. Nechť f * je Legendreova transformace funkce f . Pak pokud je vlastní funkce (nabírá konečné hodnoty na neprázdné množině), pak $\operatorname {Conv}f$

f^{{**}}=\overline {\operatorname {Conv}}f

$\overline {\operatorname {Conv}}f$ je konvexní uzávěr f , tj. funkce, jejíž epigraf je uzávěr f .

Viz také

Literatura

Polovinkin E. S., Balashov M. V. Prvky konvexní a silně konvexní analýzy. - M. : Fizmatlit, 2004. - 416 s. — ISBN 5-9221-0499-3 .
Praparatha F., Sheimos M. Výpočetní geometrie Úvod. - M .: Mir, 1989. - S. 478.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitola 33 Výpočetní geometrie // Algoritmy: Konstrukce a analýza = Úvod do algoritmů. — 2. vydání. - M .: "Williams" , 2005. - ISBN 5-8459-0857-4 .
Laszlo M. Výpočetní geometrie a počítačová grafika v C++. - M. : BINOM, 1997. - S. 304.
Levitin A. V. Kapitola 3. Metoda hrubou silou: Hledání konvexního trupu // Algoritmy. Úvod do vývoje a analýzy - M .: Williams , 2006. - S. 157. - 576 s. — ISBN 978-5-8459-0987-9
G. G. Magaril-Iljajev , V. M. Tichomirov. Konvexní analýza a její aplikace. Ed. 2., opraveno. — M.: Redakční URSS. 2003. - 176 s. — ISBN 5-354-0262-1.

Poznámky

↑ Daniel Helper, kurz "Building Algorithms", University of Haifa .