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

Pondeli od 9:00 v S8

ZKOUSKY: Terminy jsou vypsany v SISu. Vypisu jeste jeden termin v tydnu 1.-5.2. Pokud mate zajem v tomto tydnu prijit na zkousku, napiste mi sve preference. P.V.

ZAPOCTY: zapocet vam bude zapsan u zkousky (mate-li na nej narok).

Seznam odprednesene latky najdete na konci teto stranky.

Stranka cviceni.

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 5.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).
• Veta o oddelovani nadrovinou (jen princip dukazu pro ostre oddelovani kompaktnich konvexnich mnozin), priklady ukazujici, ze je pro ostre oddelovani potreba uzavrenost obou a kompaktnost aspon jedne z mnozin.
• Zadan domaci ukol c. 1 (viz www stranku cviceni).

Prednaska 12.10. (JM)

• Farkasovo lemma a veta o oddelovani.
• Radonova veta (s dukazem).
• Hellyho veta, dukaz z Radonovy vety.
• Nekonecna verze Hellyho vety.
• Pojem centra konecne mnoziny v R^d, veta o centru.
• Veta o sendvici (pro konecne mnoziny vR^d, bez dukazu).
• Zadan domaci ukol c. 2 (viz www stranku cviceni).

Prednaska 19.10. (JM)

• Minkowskeho veta (pro standardni mrizku Z^d).
• Pouziti: priklad o lesiku; aproximace realneho cisla racionalnim.
• Incidence bodu a primek, definice veliciny I(m,n), zneni Szemerediho-Trotterovy vety.
• Erdosuv problem jednotkovych vzdalenosti, funkce U(n), souvislost s incidencemi bodu a jednotkovych kruznic.

Prednaska 26.10. (JM)

• Veta o prusecikovem cisle, dukaz (pravdepodobnostni).
• Dukaz Szemerediho-Trotterovy vety (horniho odhadu).
• Dolni odhad v Szemerediho-Trotterove vete (priklad s mrizkou k x 4k^2).

Prednaska 2.11. (JM)

• Definice geometricke duality, zakladni vlastnosti.
• 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, simplex, pravidelny d-simplex reprezentovany v R^{d+1}.

Prednaska 9.11. (PV)

• Stena mnohostenu, dimenze mnohostenu. Vrchol, hrana, faseta. Priklady (krychle, ...). li> Graf mnohostenu, Steinitzova veta (bez dukazu).
• Svaz sten mnohostenu, dualita "prevraci" svaz sten. Ilustrace na prikladech.
• Simplicialni mnohosten, jednoduchy mnohosten. Okoli vrcholu jednoducheho mnohostenu: kombinatoricky vypada jako okoli vrcholu d-dimenzionalni krychle.
• P je jednoduchy prave kdyz P^* je simplicialni
• Upper bound theorem (formulace asympt. verze)
• momentova krivka, kazdych d bodu na ni je af. nezavislych
• cyklicky mnohosten

Prednaska 16.11. (PV)

• Galeovo kriterium.
• Asymptoticky dolni odhad poctu faset cykl. mnohostenu.
• Dukaz horniho odhadu asymptoticke verze Upper Bound theoremu (pouziti perturbace bez dukazu -vice ve skriptech)
• 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.

Prednaska 23.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).
• 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 (dukaz za pouziti nedokazovaneho horniho odhadu na E[|R|^[d/2]] )

Prednaska 30.11. (JM)

Prednaska 7.12. (JM)

• Arrangement mnoziny usecek, problem maximalni slozitosti jedne steny. Definice arrangementu pro obecne mnoziny v R^d.
• Nulove mnoziny mnohoclenu. Znamenkove posloupnosti. Formulace vety o maximalnim poctu znamenkovych posloupnosti a maximalnim poctu sten arrangementu nulovych mnozin. (Dukaz tezky, zcela nad moznosti teto prednasky.)
• Arrangement pseudoprimek. Isomorfismus. Narovnatelnost.

Prednaska 14.12. (PV)

• Wiring diagram. Priklad nenarovnatelneho arrangementu (z Pappovy vety).
• Pocet neisomorfnich jednoduchych arrangementu n pseudoprimek je aspon 2^{const.n^2}. (Jednoduchy arrangement pseudoprimek je takovy, v kterem zadne 3 pseudoprimky nemaji spolecny pusecik.) Pocet neisomorfnich jednoduchych arrangementu n primek je nejvys 2^{O(n log n)}.
• pulici primky, pulici usecky, 2 priklady
• pozorovani: pulicich primek (usecek) je vzdy alespon n/2
• lemma: pulici usecky tvori u kazdeho bodu (vrcholu) "hvezdici" (dukaz rotaci primky)
• nejlepsi zname odhady na maximalni pocet pulicich primek se vyrazne lisi (dolni je horsi nez n^{1+epsilon}, horni je O(n^{4/3}) )
• rovnice pro graf pul. usecek ( cr(G)+...= n/2 nad 2 ), jeji overeni pro body v obecne poloze, priste jeji dukaz pro lib. mnozinu

Prednaska 4.1. (PV)

• dukaz rovnice pro graf pulicich usecek ( cr(G)+...= n/2 nad 2 ) pro libovolne body v obecne poloze (ukazali jsme, ze spojitym posunovanim bodu se leva strana rovnice nemeni)
• dusledek: maximalni pocet pulicich primek je O(n^{4/3}), toto je nejlepsi znamy horni odhad
• konvexni nezavislost
• mezi 5 body v obecne poloze najdeme vzdy ctyri konvexne nezavisle
• Erdos-Szekeresova veta, k-misky, k-cepice, zacatek dukazu Erdos-Szekeresovy vety

Prednaska 11.1. (PV)

• dokonceni dukazu Erdos-Szekeresovy vety (dokazali jsme, ze max. velikost mnoziny bodu bez k-misky a bez l-cepice je k+l-4 nad k-2)
• male pripady, nejlepsi zname odhady v Erdos-Szekeresove vete
• konstrukce 2 na k-2 bodu bez konvexniho k-uhelniku