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

Pondělí od 9 v posluchárně S4, cvičení pak zhruba každý druhý týden po přednášce, od 10:40 v S6.

Seznam odprednesene latky najdete na konci teto stranky.

Zde stránka cvičení

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 10.10. (JM)

• zakladni pojmy: d-dim. prostor R^d (= mn. usp. d-tic realnych cisel), nadrovina, uzavr. poloprostor.
• afinni podprostor, afinni obal, afinni nezavislost.
• Konvexni mnozina, konvexni obal, je roven mnozine vsech konvexnich kombinaci (naznak dukazu).
• Caratheodoryho veta, Radonova veta, Hellyho veta - zatim jen zneni.
• Zadan domaci ukol c. 1 (viz www stranku cviceni).

Prednaska 17.10. (JM)

• Veta o oddelovani nadrovinou (neostrem, ostrem). Princip dukazu pro ostre oddelovani.
• Farkasovo lemma, jeho odvozeni z oddelovaci vety.
• Radonova veta (s dukazem).
• Hellyho veta, dukaz z Radonovy vety.
• Nekonecna verze Hellyho vety.
• Zadan domaci ukol c. 2 (viz www stranku cviceni).

Prednaska 24.10. (PV)

• Veta o centru.
• Geometricke grafy. Lemma o krizeni.
• Szemerediho-Trotterova veta o incidencich bodu a primek.
• Dusledek: Beckova veta (maximalni pocet primek s aspon k body).

Prednaska 31.10. (JM)

• Dolní odhad k Szemerediho-Trotterově větě.
• Informace o problému jednotkových vzdáleností (bez důkazů).
• Věta o sendviči (znění), Borsukova-Ulamova věta (znění), věta o centrální travsverzále (znění).
• Minkowského věta.

Přednáška 7.11. (JM)

• Příklad s lesíkem. Aproximace reálného čísla zlomkem.
• Mřížka generovaná lineárně nezávislými vektory, báze a determinant mřížky (nezávisí na volbě báze). Poznámky o použití mřížek (např. problémy pakování těles).
• Minkowského věta pro obecné mřížky.
• Každé prvočíslo kongruentní 1 modulo 4 se dá vyjádřit jako součet dvou čtverců.
• Konvexní mnohostěny: definice H-mnohostěnu a V-mnohostěnu. Konstrukce mnohostěnu z množinového systému.

Přednáška 14.11. (JM)

• Geometrická dualita a její vlastnosti.
• Každý H-mnohostěn je také V-mnohostěnem. Opačná implikace plyne pomocí duality - ponecháno k samostatnému rozmyšlení.
• d-dimenzionální krychle, zobecněný osmistěn, simplex (různé poisy, bez důkazů).
• Definice stěny, názvy stěn dimenzí 0,1,d-1.

Přednáška 21.11. (JM)

• Vlastnosti stěn; svaz stěn; kombinatorická ekvivalence mnohostěnů; graf mnohostěnu; Steinitzova věta; Balinského věta; dualita převrací svaz stěn; jednoduché a simpliciální mnohostěny [vše bez důkazů].
• f-vektor mnohostěnu. f-vektory v dimenzi 2,3.
• Momentová křivka, lemma o jejích vlastnostech. Definice cyklického mnohostěnu.

Prednaska 28.11. (PV)

• Asymptoticky dolni odhad poctu faset cykl. mnohostenu.
• Dukaz horniho odhadu asymptoticke verze Upper Bound theoremu (pouziti perturbace bez dukazu - vice ve skriptech)

Prednaska 5.12. (PV)

• Voroneho diagram pro mnozinu n bodu v R^d. Motivace: napr. posty.
• Pozorovani: kazda oblast je prunikem n-1 poloprostoru (a tedy konvexni polyedr). Z toho vyplyva (nepresny) odhad celkove slozitosti V. diagramu O(n^([d/2]+1)).
• Jednotkovy paraboloid.
• Voroneho diagram v R^d jako projekce (d+1)-dimenzionalniho konvexniho polyedru. Tedy slozitost V. diagramu je O(n^([(d+1)/2])) (dusledek Upper Bound Theoremu). Toto je asymptoticky optimalni (bez dukazu).
• 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
• Hladiny, veta o hladinach (zneni, jeji vyznam v meznich hodnotach)

Prednaska 12.12. (PV)

• Veta o hladinach (dukaz za pouziti nedokazovaneho horniho odhadu na E[|R|^[d/2]] ).
• Zona nadroviny v arrangementu n nadrovin, jednoduche odhady na slozitost zony nadroviny: dolni radove n na (d-1), horni radove n^d.
• Veta o zone nadroviny v arrangementu nadrovin.
• Dukaz vety o zone v rovine. (Dukaz pro vetsi d vynechan.)

Prednaska 19.12. (JM)

• Uvodni poznamky o algoritmech vypocetni geometrie (pozor na implementace v plovouci carce, bez specialnich technik nejsou spolehlive, lepe pouzit existujicich knihoven, napr. CGAL).
• Nektere zakladni myslenky geometrickych algoritmu: rozdel a panuj (obecny algoritmicky princip), "zametani" roviny, inkrementalni konstrukce.
• Inkrementalni konstrukce arrangementu primek v rovine (optimalni casova slozitost pomoci vety o zone).
• Inkrementalni algoritmus na konvexni obal bodu v rovine (vkladani bodu zleva doprava); jen strucne - obvykle se bere v jinem informatickem predmetu.
• Pravdepodobnostni QUICKSORT - uvod.

Prednaska 9.1.2012 (JM)

• Analyza pravdepodobnostniho QUICKSORTU - horni odhad pro prumerny pocet porovnani pri nahodnem poradi vstupnich prvku (analyza pozpatku).
• Problem lokalizace bodu v rovine. Prevod na lokalizaci v lichobeznikovem rozkladu pro n usecek. Pravdepodobnostni inkrementalni algoritmus (graf historie, lokalizace v nem). Horni odhad pro prumerny cas lokalizace (analyzu pametove narocnosti a casu predzpracovani jsme nedelali).