Kupera runko

Joukon kupera runko on pienin kupera joukko, joka sisältää . "Pienin joukko" tarkoittaa tässä pienintä elementtiä joukkojen upotuksen suhteen, toisin sanoen kuperaa joukkoa, joka sisältää tietyn kuvion siten, että se sisältyy mihin tahansa muuhun kuperaan joukkoon, joka sisältää tietyn kuvion. $X$ $X$

Tyypillisesti konveksi runko määritellään vektoriavaruuden osajoukoille reaalien yläpuolella (erityisesti euklidisessa avaruudessa ) ja vastaavissa affiineissa .

Joukon kupera runko on yleensä merkitty . $X$ $\operaattorin nimi {Conv}X$

Esimerkki

Kuvittele lauta, johon on lyöty monia nauloja - mutta ei päähän. Ota köysi, sido siihen liukulenkki ( lasso ) ja heitä se laudalle ja kiristä se. Köysi ympäröi kaikkia nauloja, mutta se koskettaa vain joitakin uloimpia nauloja. Tässä asennossa silmukka ja sen ympäröimä levyn alue ovat kupera kuori koko naularyhmälle [1] .

Ominaisuudet

$X$ on kupera joukko jos ja vain jos . $\operatorname {Conv} X=X$
Lineaarisen avaruuden mielivaltaiselle osajoukolle on olemassa ainutlaatuinen kupera runko - tämä on kaikkien konveksien joukkojen leikkauspiste, jotka sisältävät . $X$ $\operaattorin nimi {Conv}X$ $X$
- Jossa $\operaattorinimi {Conv}X=\bigcup _{{n=1}}^({\infty }}~\bigcup _{{a_{1},\dots ,a_{n}\in X}}~\bigcup _{{\lambda _{1}+\pisteet +\lambda _{n}=1)){\lambda _{1}a_{1}+\pisteet +\lambda _{n}a_{n)), ~\lambda _{i}\geq 0$
- Lisäksi, jos tilan ulottuvuus on yhtä suuri , seuraava Carathéodoryn lause on tosi : $N$ $\operaattorin nimi {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$
Tasossa olevan äärellisen pistejoukon kupera runko on kupera litteä monikulmio (degeneroituneissa tapauksissa jana tai piste), ja sen kärjet ovat alkuperäisen pistejoukon osajoukko. Samanlainen tosiasia pätee moniulotteisen avaruuden äärelliselle pistejoukolle.
Kupera runko on yhtä suuri kuin kaikkien niiden puolivälien leikkauspiste, jotka sisältävät . $X$ $X$
Krein-Milmanin lause . Paikallisesti kuperassa tilassa oleva kupera kompakti osuu yhteen sen ääripisteiden joukon kuperan rungon sulkemisen kanssa $K$ $L$ $E(K)$

Muunnelmia ja yleistyksiä

Funktion f kupera runko on sellainen funktio , että $\operaattorinimi {Conv}f$

\operaattorinimi {epi}\;\operaattorinnimi {Conv}f=\operaattorinimi {Conv}\;\operaattorinnimi {epi}f

missä epi f on funktion f epigrafi .

On syytä huomata yhteys funktion konveksin rungon käsitteen ja ei-konveksien funktioiden Legendre-muunnoksen välillä. Olkoon f * funktion f Legendre-muunnos . Sitten jos on ominaisfunktio (ottaa äärelliset arvot ei-tyhjältä joukolta), niin $\operaattorinimi {Conv}f$

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

$\overline {\operaattorin nimi {Conv}}f$ on f :n konveksi sulkeuma , eli funktio, jonka epigrafi on f :n sulkeminen .

Katso myös

Kirjallisuus

Polovinkin E.S., Balashov M.V. Kuperan ja vahvasti kuperan analyysin elementit. - M .: Fizmatlit, 2004. - 416 s. — ISBN 5-9221-0499-3 .
Praparatha F., Sheimos M. Laskennallinen geometria Johdanto. - M .: Mir, 1989. - S. 478.
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. Luku 33 Laskennallinen geometria // Algoritmit: rakentaminen ja analyysi = Algoritmien johdatus. – 2. painos. - M . : "Williams" , 2005. - ISBN 5-8459-0857-4 .
Laszlo M. Laskennallinen geometria ja tietokonegrafiikka C++:ssa. - M .: BINOM, 1997. - S. 304.
Levitin A. V. Luku 3. Brute Force Method: Finding the Convex Hull // Algoritmit. Johdatus kehitykseen ja analyysiin - M .: Williams , 2006. - S. 157. - 576 s. — ISBN 978-5-8459-0987-9
G. G. Magaril-Iljajev , V. M. Tikhomirov. Konveksianalyysi ja sen sovellukset. Ed. 2., korjattu. — M.: Pääkirjoitus URSS. 2003. - 176 s. — ISBN 5-354-0262-1.

Muistiinpanot

↑ Daniel Helper, kurssi "Rakennusalgoritmit", Haifan yliopisto .