Carcasă convexă

Corpul convex al unui set este cea mai mică mulțime convexă care conține . „Mulțimea cea mai mică” înseamnă aici cel mai mic element în ceea ce privește înglobarea mulțimilor, adică o mulțime convexă care conține o cifră dată, astfel încât să fie conținută în orice altă mulțime convexă care conține o figură dată. $X$ $X$

În mod obișnuit, învelișul convex este definit pentru submulțimi ale unui spațiu vectorial peste reali (în special în spațiul euclidian ) și pe spațiile afine corespunzătoare .

Corpul convex al unui set este de obicei notat cu . $X$ $\operatorname {Conv}X$

Exemplu

Imaginați-vă o placă în care sunt bătute multe cuie - dar nu până la cap. Luați o frânghie, legați o buclă de alunecare ( laso ) pe ea și aruncați-o pe tablă, apoi strângeți-o. Frânghia înconjoară toate cuiele, dar atinge doar unele dintre cele mai exterioare. În această poziție, bucla și zona plăcii înconjurate de aceasta sunt o coajă convexă pentru întregul grup de cuie [1] .

Proprietăți

$X$ este o mulțime convexă dacă și numai dacă . $\operatorname {Conv} X=X$
Pentru o submulțime arbitrară a unui spațiu liniar , există o carcasă convexă unică - aceasta este intersecția tuturor mulțimilor convexe care conțin . $X$ $\operatorname {Conv}X$ $X$
- în care $\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$
- În plus, dacă dimensiunea spațiului este egală atunci următoarea teoremă Carathéodory este adevărată : $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$
Învelișul convex al unui set finit de puncte de pe plan este un poligon plat convex (în cazuri degenerate, un segment sau un punct), iar vârfurile sale sunt o submulțime a setului original de puncte. Un fapt similar este valabil pentru un set finit de puncte dintr-un spațiu multidimensional.
Corpul convex este egal cu intersecția tuturor semi - spațiilor care conțin . $X$ $X$
Teorema Krein-Milman . O compactă convexă într-un spațiu local convex coincide cu închiderea carcasei convexe a setului de puncte extreme ale acestuia. $K$ $L$ $E(K)$

Variații și generalizări

Învelișul convex al unei funcții f este o funcție astfel încât $\operatorname {Conv}f$

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

unde epi f este epigraful funcției f .

Este de remarcat legătura dintre conceptul de înveliș convex al unei funcții și transformarea Legendre a funcțiilor neconvexe. Fie f * transformata Legendre a funcției f . Atunci, dacă este o funcție proprie (ia valori finite pe o mulțime nevide), atunci $\operatorname {Conv}f$

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

$\overline {\operatorname {Conv}}f$ este o închidere convexă a lui f , adică o funcție a cărei epigrafă este închiderea lui f .

Vezi și

Literatură

Polovinkin E. S., Balashov M. V. Elemente de analiză convexă și puternic convexă. - M. : Fizmatlit, 2004. - 416 p. — ISBN 5-9221-0499-3 .
Praparatha F., Sheimos M. Computational Geometry O introducere. - M . : Mir, 1989. - S. 478.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Capitolul 33 Geometrie computațională // Algoritmi: Construcție și analiză = Introducere în algoritmi. — ediția a II-a. - M . : „Williams” , 2005. - ISBN 5-8459-0857-4 .
Laszlo M. Geometrie computațională și grafică pe computer în C++. - M. : BIOM, 1997. - S. 304.
Levitin A. V. Capitolul 3. Metoda forței brute: Găsirea corpului convex // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - P. 157. - 576 p. — ISBN 978-5-8459-0987-9
G. G. Magaril-Ilyaev , V. M. Tikhomirov. Analiza convexă și aplicațiile sale. Ed. al 2-lea, corectat. — M.: Editorial URSS. 2003. - 176 p. — ISBN 5-354-0262-1.

Note

↑ Daniel Helper, curs „Building Algorithms”, Universitatea din Haifa .