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

NOVINKA: od 14. listopadu se cas meni na 10:40, v SW2 (prizemi)

cviceni potom od 12:20 v S1

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

Prednaska 17.10.(JM) Jista verze Farkasova lemmatu, dukaz z vety o oddelovani (potrebujeme ostre oddelit kompaktni konvexni mnozinu od bodu). Kratke vysvetleni pojmu linearni programovani (v tomto oboru je Farkasovo lemma dulezite). Poznamka, jak se da dokazat uzavrenost konvexniho obalu konecne mnoziny bodu, zavedeni standardniho simplexu \Delta^{n-1} v R^n. Radonovo lemma s dukazem. Hellyho veta s dukazem (z Radonova lemmatu). Poznamka o Hellyho vete pro nekonecny soubor mnozin. Definice centra konecne mnoziny, veta o centru (zatim jen formulace).

Prednaska 24.10.(JM) zrusena pro minimalni ucast posluchacu. Ze skript je potreba nastudovat nasledujici: dukaz very o centru, zneni vety o sendvici a vety o centralnich transversalach, a dale z kapitoly Incidence problems uvodni cast (specialne definice I(m,n), U(n), g(n), zneni Szemerediho-Trotterovy vety) a dolni odhad pro I(n,n), tj. prvni cast druhe sekce. V dalsi prednasce na toto navazeme.

Prednasky 1. a 7. 11.(JM) Lemma o prusecikovem cisle s dukazem, dukaz Szemerediho-Trotterovy vety. Definice geometricke duality, zakladni vlastnosti.

Prednaska 14. 11.(JM) Definice dualni mnoziny X^*, jeji vyjadreni jako prunik poloprostoru, fakt (cviceni) (X^*)^*=X pro konvexni uzavrene X obsahujici 0. Definice H-mnohostenu a V-mnohostenu, rozdily z algoritmickeho hlediska, veta o ekvivalenci obou pojmu (poradne jsme dokazali, ze kazdy H-mnohosten je taky V-mnohosten, obracena implikace jen naznak dukazu pomoci duality). Priklady: krychle, zobecneny osmisten (3 vyjadreni), simplex, pravidelny d-simplex reprezentovany v R^{d+1}. Stena mnohostenu, priklady (pro 3dim krychli). Extremalni bod. Zakladni tvrzeni o stenach ("extremalni body jsou presne vrcholy neboli 0-steny", "stena steny je stena" - bez dukazu).

Prednaska 21. 11.(JM) Graf mnohostenu, Steinitzova veta (bez dukazu), Balinskeho vete (bez dukazu). Svaz sten mnohostenu. Dualni mnohosten, dualita "prevraci" svaz sten. Ilustrace na prikladech. Simplicialni mnohosten, jednoduchy mnohosten.

Prednaska 28. 11.(JM) Momentova krivka, cyklicky mnohosten, Galeovo kriterium, pocet facet cyklickeho mnohostenu. Upper Bound Theorem (jen zneni), asymptoticka verze, dukaz zatim jen pro simplicialni mnohosteny.

Prednaska 5.12. (Jan Kyncl)

• pozorovani, ze z 5 bodu v obecne poloze lze vybrat 4 konvexne nezavisle
• Erdosova-Szekeresova veta, 1. dukaz - z Ramseyovy vety
• definice f(k), zname odhady
• 2. dukaz - f(k) <= (2k-4 \choose k-2) +1, pomoci presneho odhadu pro velikost mnoziny bez k-misky a l-cepice: h(k,l)=(k+l-4 \choose k-2) +1 (dukaz horniho odhadu i konstrukce pro dolni odhad)
• konstrukce mnoziny 2^(k-2) bodu bez k-prvkove konvexni podmnoziny
• definice k-diry a funkce g(k), zname odhady pro g(k)
• veta o existenci 5-diry v mnozine f(6) bodu (g(5)<=f(6))
• veta o neexistenci 7-diry, konstrukce Hortonovskych mnozin velikosti 2^n.

Prednaska 12.12. (JM) Lemma: pro kazdy d-dim konvexni mnohosten P s n vrcholy existuje simplicialni mnohosten Q s n vrcholy, splnujici f_k(P) <= f_k(Q) pro vsechna k (myslenka dukazu - vhodna perturbace, dukaz vynechan). Voroneho diagram mnoziny n bodu v R^d. Kazda oblast je prunikem n-1 poloprostoru. Poznamka o aplikacich a o Delaunayove triangulaci. Souvislost Voroneho diagramu v R^d s konvexnimi polyedry v R^{d+1}, dusledky: algoritmicky, odhad max. poctu sten. Arrangementy nadrovin - definice, pojem jednoducheho arrangementu, fakt bez dukazu - pocet k-sten pro dany pocet nadrovin je maximalizovan pro jednoduchy arrangement.