Konvext skrov

Det konvexa skrovet på en uppsättning är den minsta konvexa uppsättningen som innehåller . "Minsta uppsättning" betyder här det minsta elementet med avseende på inbäddningen av uppsättningar, det vill säga en konvex uppsättning som innehåller en given figur så att den ingår i någon annan konvex uppsättning som innehåller en given figur. $X$ $X$

Vanligtvis definieras det konvexa skrovet för delmängder av ett vektorrum över realerna (särskilt i det euklidiska utrymmet ) och på motsvarande affina utrymmen .

Det konvexa skrovet på en uppsättning betecknas vanligtvis med . $X$ $\operatörsnamn {Conv}X$

Exempel

Föreställ dig en bräda där många spikar slås in - men inte till själva huvudet. Ta ett rep, knyt en glidögla ( lasso ) på det och släng det på brädan och dra sedan åt det. Repet omger alla spikarna, men det berör bara några av de yttersta. I det här läget är öglan och området på brädan som omges av den ett konvext skal för hela gruppen av spikar [1] .

Egenskaper

$X$ är en konvex uppsättning om och endast om . $\operatorname {Conv} X=X$
För en godtycklig delmängd av ett linjärt utrymme finns det ett unikt konvext skrov - detta är skärningspunkten för alla konvexa uppsättningar som innehåller . $X$ $\operatörsnamn {Conv}X$ $X$
- Vart i $\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$
- Dessutom, om rummets dimension är lika, är följande Carathéodory-sats sann : $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 konvexa skrovet av en ändlig uppsättning punkter på planet är en konvex platt polygon (i degenererade fall, ett segment eller en punkt), och dess hörn är en delmängd av den ursprungliga uppsättningen av punkter. Ett liknande faktum är sant för en ändlig uppsättning punkter i ett flerdimensionellt utrymme.
Det konvexa skrovet är lika med skärningspunkten mellan alla halvutrymmen som innehåller . $X$ $X$
Krein-Milman-satsen . En konvex kompakt i ett lokalt konvext utrymme sammanfaller med stängningen av det konvexa skrovet på uppsättningen av dess extrempunkter $K$ $L$ $E(K)$

Variationer och generaliseringar

Det konvexa skrovet för en funktion f är en funktion sådan att $\operatörsnamn {Konv}f$

\operatörsnamn {epi}\;\operatörsnamn {Konv}f=\operatörsnamn {Konv}\;\operatörsnamn {epi}f

där epi f är epigrafen för funktionen f .

Det är värt att notera sambandet mellan konceptet med det konvexa skrovet för en funktion och Legendre-transformationen av icke-konvexa funktioner. Låt f * vara Legendre-transformen av funktionen f . Sedan om är en egenfunktion (tar ändliga värden på en icke-tom uppsättning), då $\operatörsnamn {Konv}f$

f^{{**}}=\overline {\operatörsnamn {Conv}}f

$\overline {\operatörsnamn {Conv}}f$ är en konvex stängning av f , det vill säga en funktion vars epigraf är stängningen av f .

Se även

Litteratur

Polovinkin E. S., Balashov M. V. Element av konvex och starkt konvex analys. - M. : Fizmatlit, 2004. - 416 sid. — 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 Beräkningsgeometri // Algoritmer: Konstruktion och analys = Introduktion till algoritmer. — 2:a upplagan. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
Laszlo M. Beräkningsgeometri och datorgrafik i C++. - M. : BINOM, 1997. - S. 304.
Levitin A. V. Kapitel 3. Brute Force Method: Hitta det konvexa skrovet // Algoritmer. Introduktion till utveckling och analys - M. : Williams , 2006. - P. 157. - 576 sid. — ISBN 978-5-8459-0987-9
G. G. Magaril-Ilyaev , V. M. Tikhomirov. Konvex analys och dess tillämpningar. Ed. 2:a, korrigerad. — M.: Redaktionell URSS. 2003. - 176 sid. — ISBN 5-354-0262-1.

Anteckningar

↑ Daniel Helper, kurs "Byggalgoritmer", University of Haifa .