Konvekst skrog

Det konvekse skrog af et sæt er det mindste konvekse sæt, der indeholder . "Mindste sæt" betyder her det mindste element med hensyn til indlejring af sæt, det vil sige et konveks sæt, der indeholder en given figur, således at den er indeholdt i ethvert andet konveks sæt, der indeholder en given figur. $x$ $x$

Typisk er det konvekse skrog defineret for delmængder af et vektorrum over realerne (især i det euklidiske rum ) og på de tilsvarende affine rum .

Det konvekse skrog af et sæt er normalt betegnet med . $x$ $\operatørnavn {Konv}X$

Eksempel

Forestil dig et bræt, hvor der slås mange søm i – men ikke helt til hovedet. Tag et reb, bind en glidende løkke ( lasso ) på det og smid det på brættet, og stram det så. Rebet omgiver alle sømmene, men det rører kun nogle af de yderste. I denne position er løkken og området af brættet omgivet af det en konveks skal for hele gruppen af søm [1] .

Egenskaber

$x$ er et konveks sæt hvis og kun hvis . $\operatorname {Konv} X=X$
For en vilkårlig delmængde af et lineært rum er der et unikt konveks skrog - dette er skæringspunktet mellem alle konvekse sæt indeholdende . $x$ $\operatørnavn {Konv}X$ $x$
- Hvori $\operatorname {Conv}X=\bigcup _{{n=1}}^({\infty }}~\bigcup _{{a_{1},\dots ,a_{n}\in X}}~\bigcup _{{\lambda _{1}+\dots +\lambda _{n}=1)){\lambda _{1}a_{1}+\dots +\lambda _{n}a_{n)), ~\lambda _{i}\geq 0$
- Desuden, hvis dimensionen af rummet er ens , er følgende Carathéodory-sætning sand : $N$ $\operatorname {Conv}X=\bigcup _{{a_{1},\dots ,a_{{N+1}}\in X}}\bigcup _{{\lambda _{1}+\dots +\lambda _{{N+1}}=1}}{\lambda _{1}a_{1}+\dots +\lambda _{{N+1}}a_{{N+1}}},~\lambda _{i}\geq 0$
Det konvekse skrog af et endeligt sæt punkter på planet er en konveks flad polygon (i degenererede tilfælde et segment eller et punkt), og dets hjørner er en delmængde af det oprindelige sæt punkter. En lignende kendsgerning gælder for et begrænset sæt punkter i et multidimensionelt rum.
Det konvekse skrog er lig med skæringspunktet mellem alle halvrum indeholdende . $x$ $x$
Krein-Milman-sætningen . En konveks kompakt i et lokalt konveks rum falder sammen med lukningen af det konvekse skrog af sættet af dets yderpunkter $K$ $L$ $E(K)$

Variationer og generaliseringer

Det konvekse skrog af en funktion f er en funktion sådan, at $\operatornavn {Konv}f$

\operatørnavn {epi}\;\operatørnavn {Konv}f=\operatørnavn {Konv}\;\operatørnavn {epi}f

hvor epi f er epigrafen for funktionen f .

Det er værd at bemærke forbindelsen mellem konceptet med det konvekse skrog af en funktion og Legendre-transformationen af ikke-konvekse funktioner. Lad f * være Legendre-transformationen af funktionen f . Så hvis er en egenfunktion (tager endelige værdier på et ikke-tomt sæt), så $\operatornavn {Konv}f$

f^{{**}}=\overline {\operatørnavn {Konv}}f

$\overline {\operatørnavn {Konv}}f$ er en konveks lukning af f , altså en funktion hvis epigraf er lukning af f .

Se også

Litteratur

Polovinkin E. S., Balashov M. V. Elementer af konveks og stærkt konveks analyse. - M. : Fizmatlit, 2004. - 416 s. — ISBN 5-9221-0499-3 .
Praparatha F., Sheimos M. Computational Geometry En introduktion. - M . : Mir, 1989. - S. 478.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Kapitel 33 Beregningsgeometri // Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. — 2. udgave. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
Laszlo M. Beregningsgeometri og computergrafik i C++. - M. : BINOM, 1997. - S. 304.
Levitin A. V. Kapitel 3. Brute Force Metode: Find det konvekse skrog // Algoritmer. Introduktion til udvikling og analyse - M. : Williams , 2006. - S. 157. - 576 s. — ISBN 978-5-8459-0987-9
G. G. Magaril-Ilyaev , V. M. Tikhomirov. Konveks analyse og dens anvendelser. Ed. 2., rettet. — M.: Redaktionel URSS. 2003. - 176 s. — ISBN 5-354-0262-1.

Noter

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