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

Prednaska: utery 14:00 S9. Cviceni: utery 15:40 S9.

ZKOUSKY:
Predterminy: mate-li zajem, napiste email na valtr zavinac kam atd.
Radne terminy najdete v SIS. Mist je na kazdem terminu dostatek, ale na zapsani potrebujete zapocet. Zapocty budu prubezne zapisovat do SIS s tim, jak se budou objevovat na strance cviceni (poprve je zapisu kolem 8.1.). Do indexu Vam bude zapocet zapsan u zkousky.
Zkouska je ustni. Zkousi se odprednesene vcetne dukazu a schopnost naucene znalosti aplikovat pri reseni primerene obtiznych prikladu (obdobneho typu jako byly zapoctove priklady).

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 2.10. (PV)

• 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.
• Afinni podprostor, afinni obal, afinni nezavislost.
• Caratheodoryho veta (dukaz v ramci ukolu na cviceni), Radonova veta - zatim jen zneni.
• Zadan domaci ukol c. 1 (viz www stranku cviceni).

Prednaska 9.10. (PV)

• Radonova veta (s dukazem).
• Hellyho veta, dukaz z Radonovy vety.
• Nekonecna verze Hellyho vety.
• Veta o oddelovani nadrovinou.
• Nekolik prikladu (nelze uvazovat otevrene poloprostory, a to ani pro uzavrene mnoziny).
• Dukaz vety o oddelovani nadrovinou: 1. pro jednu mnozinu uzavrenou a pro druhou kompaktni, 2. (naznak) pro libovolne mnoziny.
• Zadan domaci ukol c. 2 (viz www stranku cviceni).

Prednaska 16.10. (PV)

• centrum konecne mnoziny bodu, veta o centru.
• priklad: veta o centru nejde zesilit.
• Minkowskeho veta pro mrizku.
• Napoveda k domacimu ukolu c. 1.

Prednaska 23.10. (PV)

• Mřížka generovaná lineárně nezávislými vektory, báze a determinant mřížky (nezávisí na volbě báze).
• Minkowského věta pro obecné mřížky.
• Dusledek: kazde prvocislo kongruentni 1 modulo 4 lze napsat jako soucet dvou ctvercu celych cisel. (Bez dukazu)
• Věta o sendviči (bez dukazu), věta o centrální travsverzále (bez dukazu).
• Vety o sendvici a o centru jsou specialnim pripadem vety o centralni transverzale.
• Geometrická dualita a její vlastnosti.
• Napoveda k domacimu ukolu c. 2, zadan domaci ukol c. 3 (viz www stranku cviceni).

Prednaska 30.10. (JM)

• konvexni mnohosteny: priklady, V-polytop, H-polytop, jejich ekvivalence (s dukazem).
• steny mnohostenu, dimenze steny, vchol, hrana, faseta.

Prednaska 6.11. (JM)

• Zakladni vlastnosti sten mnohostenu. Graf mnohostenu, Steinitzova veta, poznamka o Koebeho vete, poznamka o Hirschove domnence (vse bez dukazu).
• Svaz sten, kombinatoricka ekvivalence, svaz sten dualniho mnohostenu (opet bez dukazu).
• Jednoduche a simplicialni mnohosteny.

Prednaska 13.11. (JM)

• f-vektor mnohostěnu. f-vektory v dimenzi 2,3.
• Momentová křivka, lemma o jejích vlastnostech. Definice cyklického mnohostěnu C(d,n). Galeovo kriterium. Počet faset C(d,n).
• Upper Bound Theorem. Asymptoticka verze. Dukaz horniho odhadu asymptoticke verze Upper Bound theorem Dukaz zatim pro simplicialni mnohosteny.

Prednaska 20.11. (PV)

• Dukaz horniho odhadu asymptoticke verze Upper Bound theorem pro libovolne mnohosteny (pomoci perturbace - maleho posunuti vrcholu)
• Voroneho diagram: motivace (posty), definice Voroneho diagramu pro konecne mnoziny bodu v d-dim prostoru,
• 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.
• Napoveda k domacimu ukolu c. 4

Prednaska 27.11. (PV)

• 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).
• Poznamka o aplikaci Voroneho diagramu: kruhovy robot pohybujici se v rovine s jednobodovymi prekazkami.
• Arrangementy nadrovin v rovine a v R^d. Stena arrangementu, bunka.
• 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.
• Zona nadroviny v arrangementu n nadrovin, zneni vety o zone.

Prednaska 4.12. (PV)

• Napoveda k domacimu ukolu c. 5.
• Jednoduche odhady na slozitost zony nadroviny: dolni radove n na (d-1), horni radove n na d.
• Dukaz vety o zone nadroviny: v rovine pocitanim hran zony vyrustajicich z jedne primky, ve vyssich dimenzich indukci podle dimenze.

Prednaska 11.12. (PV)

• Veta o hladinach (dukaz za pouziti nedokazovaneho horniho odhadu na E[|R|^[d/2]] ).
• Nektere zakladni myslenky geometrickych algoritmu (dokumentovane na vypoctu konvexniho obalu n bodu v rovine): rozdel a panuj, inkrementalni konstrukce
• "output-sensive" algoritmus Kirkpatricka a Seidela na vypocet konvexniho obalu n bodu v rovine v case O(nlogh), kde h je pocet hran vysledneho konvexniho obalu (nastin, dokonceni priste)

Prednaska 18.12. (PV)

• Napoveda k domacimu ukolu c. 6
• Dokonceni algoritmu Kirkpatricka a Seidela.
• Motivace k problemu lokalizace bodu v lichobeznikove dekompozici n neprotinajicich se usecek.
• Lichobeznikova dekompozice a vypocet prumerne slozitosti lokalizace bodu (za pouziti lichobeznikovych dekompozic pri postupnem pridavani usecek v nahodnem poradi)

ZKOUSKY: Informace na zacatku stranky