Domború hajótest

Egy halmaz konvex héja a legkisebb konvex halmaz , amely tartalmazza a . A "legkisebb halmaz" itt a halmazok beágyazásához képest a legkisebb elemet jelenti, azaz egy olyan konvex halmazt, amely egy adott alakzatot tartalmaz úgy, hogy azt bármely más, adott alakzatot tartalmazó konvex halmaz tartalmazza. $x$ $x$

A konvex burkot általában a valós értékek feletti vektortér részhalmazaira határozzák meg (különösen az euklideszi térben ) és a megfelelő affin tereken .

A halmaz konvex héját általában jelöli . $x$ $\operátornév {Conv}X$

Példa

Képzelj el egy táblát, amelybe sok szöget ütnek be – de nem egészen a fejig. Vegyünk egy kötelet, kössünk rá egy csúszóhurkot ( lasszót ), dobjuk a deszkára, majd húzzuk meg. A kötél körülveszi az összes szöget, de csak a legkülső szögeket érinti. Ebben a helyzetben a hurok és az általa körülvett tábla területe egy domború héj az egész szögcsoport számára [1] .

Tulajdonságok

$x$ akkor és csak akkor konvex halmaz . $\operatorname {Conv} X=X$
Egy lineáris tér tetszőleges részhalmazához létezik egy egyedi konvex burok – ez az összes olyan konvex halmaz metszéspontja, amely tartalmazza a . $x$ $\operátornév {Conv}X$ $x$
- Ahol $\operátornév {Conv}X=\bigcup _{{n=1}}^({\infty }}~\bigcup _{{a_{1},\dots ,a_{n}\in X}}~\bigcup _{{\lambda _{1}+\pontok +\lambda _{n}=1)){\lambda _{1}a_{1}+\pontok +\lambda _{n}a_{n)), ~\lambda _{i}\geq 0$
- Továbbá, ha a tér mérete egyenlő, akkor igaz a következő Carathéodory-tétel : $N$ $\operátornév {Conv}X=\bigcup _{{a_{1},\dots ,a_{{N+1}}\in X}}\bigcup _{{\lambda _{1}+\pontok +\lambda _{{N+1}}=1}}{\lambda _{1}a_{1}+\dots +\lambda _{{N+1}}a_{{N+1}}},~\lambda _{i}\geq 0$
A síkon egy véges ponthalmaz konvex héja egy konvex lapos sokszög (elfajult esetekben szakasz vagy pont), csúcsai pedig az eredeti ponthalmaz részhalmazai. Hasonló tény igaz egy többdimenziós tér véges ponthalmazára is.
A konvex test megegyezik a -t tartalmazó összes féltér metszéspontjával . $x$ $x$
A Krein-Milman tétel . Egy lokálisan konvex térben konvex kompakt egybeesik a szélső pontjai halmazának konvex testének záródásával $K$ $L$ $E(K)$

Változatok és általánosítások

Az f függvény konvex burka olyan függvény , hogy $\operátornév {Conv}f$

\operátornév {epi}\;\operátornév {Conv}f=\operatorname {Conv}\;\operatorname {epi}f

ahol epi f az f függvény epigráfja .

Érdemes megjegyezni a függvény konvex burok fogalma és a nem konvex függvények Legendre transzformációja közötti összefüggést. Legyen f * az f függvény Legendre transzformációja . Ekkor ha egy sajátfüggvény (véges értékeket vesz fel egy nem üres halmazon), akkor $\operátornév {Conv}f$

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

$\overline {\operatorname {Conv}}f$ f konvex lezárása , vagyis olyan függvény, amelynek epigráfja f zárása .

Lásd még

Irodalom

Polovinkin E. S., Balashov M. V. A konvex és erősen konvex elemzés elemei. - M. : Fizmatlit, 2004. - 416 p. — ISBN 5-9221-0499-3 .
Praparatha F., Sheimos M. Számítógépes geometria Bevezetés. - M . : Mir, 1989. - S. 478.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. 33. fejezet Számítógépes geometria // Algoritmusok: Konstrukció és elemzés = Bevezetés az algoritmusokba. — 2. kiadás. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
M. László Számítógépes geometria és számítógépes grafika C++ nyelven. - M. : BINOM, 1997. - S. 304.
Levitin A. V. 3. fejezet: Brute Force Method: Finding the Convex Hull // Algorithms. Bevezetés a fejlesztésbe és elemzésbe - M .: Williams , 2006. - P. 157. - 576 p. — ISBN 978-5-8459-0987-9
G. G. Magaril-Iljajev , V. M. Tikhomirov. Konvex elemzés és alkalmazásai. Szerk. 2., javítva. — M.: Szerkesztőség URSS. 2003. - 176 p. — ISBN 5-354-0262-1.

Jegyzetek

↑ Daniel Helper, „Algoritmusok építése” tanfolyam , Haifai Egyetem .