Informace k prednasce "Kombinatoricka a vypocetni geometrie I" 2008/2009
(Jiri Matousek, Pavel Valtr, KAM)

Zkouska

Pondeli od 17:20 v S10

Anotace
Vypocetni geometrie se zabyva navrhem efektivnich algoritmu pro geometricke problemy v rovine i ve vicedimenzionalnim prostoru (napr. je-li dano n bodu v rovine, jak co nejefektivneji najit dvojici bodu s nejmensi vzdalenosti). Takove problemy jsou motivovany aplikacemi v pocitacove grafice, prostorovem modelovani (napr. molekul, budov, soucastek), geografickych informacnich systemech a pod. Pri analyze takovych algoritmu se potrebuje kombinatoricka geometrie, studujici kombinatoricke vlastnosti geometrickych konfiguraci, konvexnich mnozin a pod. Vysledky jsou dulezite i z ciste matematickeho hlediska, napr. v teorii cisel. V teto uvodni prednasce se probiraji zakladni pojmy a metody, s durazem na matematicky zaklad (jine mozne podani by bylo z vice "informatickeho" hlediska, s durazem na datove struktury, implementaci algoritmu a pod.). O naplni prednasky si muzete udelat lepsi predstavu podle latky probrane v lonske prednasce.

Osnova. Zakladni vety o konvexnich mnozinach (Radonova, Hellyho veta), Minkowskeho veta, geometricka dualita, definice a zakladni vlastnosti konvexnich mnohostenu, kombinatoricka slozitost konvexnich mnohostenu (cyklicke mnohosteny), Voroneho diagram a Delaunayova triangulace, arrangementy nadrovin (pocet sten, veta o zone), strategie "zametani roviny " (hledani pruseciku usecek), strategie "pravdepodobnostni inkrementalni konstrukce ", problem lokalizace bodu, vypocet konvexniho obalu, konstrukce arrangementu, linearni programovani v male dimenzi, triangulace mnohouhelnika v rovine.

Literatura

• Skripta Jiriho Matouska Introduction to Discrete Geometry vysla v ITI Seriich (preprintova rada Institutu teoreticke informatiky MFF UK) pod cislem 2003-150 a je k dispozici v informaticke knihovne MFF UK. Tady jsou take jako postscriptovy soubor, v nemz jsou pro usporu mista 2 male stranky na jedne strance A4. Je urcen hlavne pro dvoustranny tisk a ma vlevo okraj na svazani.
• Predchozi text je ve skutecnosti vyber casti obvykle probiranych v prednasce z knihy J. Matousek: Lectures on Discrete Geometry.
• Text k casti o inkrementalnich geometrickych algoritmech je k dispozici zde (12 str).
• Standardni uvodni text o vypocetni geometrii je M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: Computational Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 1997. Informaticke oddeleni knihovny ma nekolik exemplaru.
• J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press 1995

Probrana temata

Prednaska 6.10. (P.V.)

• zakladni pojmy: d-dim. prostor R^d (= mn. usp. d-tic realnych cisel), nadrovina, uzavr. poloprostor.
• Konvexni mnozina, konvexni obal, je roven mnozine vsech konvexnich kombinaci, nekolik prikladu.
• Caratheodoryho veta (bez dukazu)
• Veta o oddelovani nadrovinou (bez dukazu), priklady ukazujici ze je pro ostre oddelovani potreba uzavrenost obou a kompaktnost aspon jedne z mnozin.
• afinni prostory, afinni obal
• Zadan domaci ukol c. 1 (mozno stahnout na www strance cviceni).

Prednaska 13.10. (P.V.)

• afinni obal, afinni kombinace, afinni zavislost
• Radonova veta (s dukazem).
• Hellyho veta, dukaz z Radonovy vety.
• nekonecna verze Hellyho vety (pouze naznak dukazu).
• centrum jakozto zobecneni medianu z primky do R^d, veta o centru, dukaz z Hellyho vety.
• Zadan domaci ukol c. 2 (mozno stahnout na www strance cviceni).

Prednaska 20.10. (P.V.)

• centrum jakozto zobecneni medianu z primky do R^d, nekolik prikladu, veta o centru, dukaz z Hellyho vety.
• prusecikove lemma (=lemma o krizeni), co rika v asymptoticky meznich pripadech
• dukaz prusecikoveho lemmatu pravdepodobnostni metodou

Prednaska 27.10. (P.V.)

• Veta o max. poctu incidenci mezi n body a l primkami, jeji dukaz z prusecikoveho lemmatu
• Geometricka dualita (nenulovemu bodu a prirazuje nadrovinu <a,x>=1, a naopak). Vlastnosti: zachovava incidenci a "lezeni v poloprostoru". Nekolik prikladu. Dualni mnozina X^*={y\in R^d: <x,y> <= 1}. Nekolik prikladu.
• V-mnohosten (konv. obal konecne mnoziny), H-mnohosten (prunik konecne mnoha uzavrenych poloprostoru).
• Veta: Kazdy V-mnohosten je H-mnohostenem, a kazdy omezeny H-mnohosten je tez V-mnohostenem.
• Dukaz prvni casti vety.
• Zadan domaci ukol c. 3 (mozno stahnout na www strance cviceni).

Prednaska 3.11. (J.M.)

• Princip dukazu druhe casti vety (z duality).
• Stena mnohostenu, priklady (pro krychli). Vrchol, hrana,faseta.
• Extremalni bod. Zakladni tvrzeni o stenach ("extremalni body jsou presne vrcholy neboli 0-steny", "stena steny je stena" - bez dukazu).
• Graf mnohostenu, Steinitzova veta (bez dukazu), Balinskeho veta (bez dukazu).
• Svaz sten mnohostenu, kombinatoricka ekvivalence. Dualni mnohosten, dualita "prevraci" svaz sten. Ilustrace na prikladech. Simplicialni mnohosten, jednoduchy mnohosten.

Prednaska 10.11. (J.M.)

• Momentova krivka, cyklicky mnohosten.
• Galeovo kriterium.
• Pocet facet cyklickeho mnohostenu.
• Upper Bound Theorem (jen zneni), asymptoticka verze. Dukaz zatim jen pro simplicialni mnohosteny.

Prednaska 24.11. (J.M.)

• Perturbace. Tvrzeni: pro kazdy d-dimenzionalni konvexni mnohosten P existuje simplicialni konvexni mnohosten P, pro nejz f_0(Q)=f_0(P) a f_k(Q) je vetsi nebo rovno f_k(P) pro kazde k. Dukaz pomoci epsilon-postrceni (vrcholu dovnitr), nedokazovali jsme 2 jednodussi tvrzeni v dukazu pouzita.
• Voroneho diagram pro mnozinu n bodu v R^d.
• Pozorovani: kazda oblast je prunikem n-1 poloprostoru (a tedy konvexni polyedr).
• Jednotkovy paraboloid. Voroneho diagram v R^d jako projekce (d+1)-dimenzionalniho konvexniho polyedru.

Prednaska 1.12. (J.M.)

• Kombinatoricka slozitost Voroneho diagramu v R^d (jako dusledek UBT).
• Arrangementy nadrovin v rovine a v R^d. Stena arrangementu, dimenze steny arrangementu. Steny spec. dimenzi: vrcholy (dim 0), hrany (dim 1), bunky (dim d).
• Pocet bunek v arrangmentu lib. n nadrovin v obecne poloze v R^d je roven souctu cisel n nad i pro i=0,1,...,d (dva dukazy).
• Poznamka o kombinatoricke slozitosti jedne steny arrangementu n usecek v rovine (je konstanta.n alpha(n), alpha(n) inverzni funkce k Ackermannove funkci) - bez dukazu.
• Obecna definice arrangementu mnozin v R^d.

Prednaska 8.12. (J.M.)

• Arrangementy nulovych mnozin mnohoclenu v R^d. Znamenkove kombinace. Hlavni veta (Oleinikova-Petrovskij-Milnor-Thom...): je-li maximalni stupen mnohoclenu D, pak je max. pocet sten arrangementui, a tedy i pocet znamenkovych posloupnosti, omezen (50nD/d)^d (d je dimenze, n pocet mnohoclenu). Bez dukazu.
• Afinni arrangement pseudoprimek. Ekvivalence dvou arrangementu. Narovnatelnost.
• Pocet neisomorfnich jednoduchych arrangementu n pseudoprimek je aspon 2^{const.n^2}. Pocet neisomorfnich jednoduchych arrangementu n primek je nejvys 2^{O(n log n)}.
• Vypocetni geometrie - uvod.
• Model vypoctu ve vypocetni geometrii: realny RAM (abstraktni pocitac s registry 1,2,3,..., v kazdem muze byt libovolne realne cislo, bezne aritmeticke operace a testy (rovnost, mensi nebo rovno) v konstantnim case.

Prednaska 15.12. (J.M.)

• Inkrementalni algoritmus pro konvexni obal v rovine (priklad amortizovane analyzy).
• Tridici algoritmus QUICKSORT. Pravdepodobnostni varianta (predpokladame, ze cisla na vstupu jsou v nahodnem poradi).

Prednaska 5.1.2009 (J.M.)

• Analyza pravdepodobnostniho QUICKSORTU: stredni hodnota poctu porovnani je nejvys 2 n ln n (analyza pozpatku).
• Problem lokalizace bodu v rovine.
• Preformulovani pomoci lichobeznikoveho rozkladu.
• Pravdepodobnostni inkrementalni algoritmus konstruujici lich. rozklad pro danych n usecek (pomocny), datova struktura "orientovany graf historie", lokalizace bodu prochazenim historie.
• Prvni cast analyzy algoritmu: Pro kazde pevne x je stredni hodnota poctu lichobezniku v historii, ktere x obsahuji, nejvys O(log n).

Prednaska 12.1.2009 (J.M.)

• Dokonceni analyzy: detaily konstrukce datove struktury, stredni hodnota casove slozitosti konstrukce a pameti.
• Erdosova-Szekeresova veta. Funkce f(k,l) (k-miska nebo l-cepice), horni odhad (rekurence f(k,l) nejvys f(k-1,l)+f(k,l-1)-1), dolni odhad (induktivni konstrukce mnoziny X_{k,l} bez k-misek a bez l-cepic).