Informace k prednasce "Kombinatoricka a vypocetni geometrie I" 2010/2011
(Jiri Matousek, Pavel Valtr, KAM)
Pátek od 14:00 v S10, cvičení: viz odkaz o kousek nize.
Seznam odprednesene latky najdete na konci teto stranky.
ZKOUSKY (terminy): Prof. Matousek vypsal v SIS 4 terminy v lednu.
Komu se zadny z nich nehodi, nevahejte mi napsat na valtr-zavinac-kam... a
na nejakem jinem terminu se domluvime. Ve vlastnim zajmu radeji piste
s predstihem alespon 1 tydne. P.Valtr
Stranka cviceni.
Rozsah vyuky: ZIMNI semestr 2/2 Z, Zk
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 8.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 (naznak dukazu).
- Veta o oddelovani nadrovinou,
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 15.10. (PV)
- Afinni podprostor, afinni obal, afinni nezavislost.
- 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 (nastin zneni ve 3 dimenzich).
- Zadan domaci ukol c. 2 (viz
www stranku cviceni).
Prednaska 22.10. (PV)
- geometricky graf, topologicky graf
- prusecikova cisla grafu
- lemma o prusecikovem cisle (crossing lemma), pravdepodobnostni dukaz
- dukaz vety Szemerediho a Trottera z crossing lemmatu
Prednaska 5.11. (PV)
- konstrukce n bodu a n primek v rovine s cn^{4/3} incidencemi bod-primka
- otazka max. poctu jednotkovych vzdalenosti mezi n body v rovine:
zname dohady a nastin dolniho odhadu (mrizka)
- konvexni mnohosteny: priklady, V-mnohosten, H-mnohosten
- steny mnohostenu, dimenze steny, vchol, hrana, faseta
- geometricka dualita, dualni mnozina (priklady, jednoducha tvrzeni)
- svaz sten mnohostenu (nastin)
Prednaska 12.11. (JM)
- Simplicialni mnohosten, jednoduchy mnohosten.
- Momentova krivka,
cyklicky mnohosten, Galeovo kriterium, pocet facet
cyklickeho mnohostenu. Upper Bound Theorem (jen zneni).
Prednaska 19.11. (JM)
- Asymptoticka veta o hornim odhadu, dukaz vcetne perturbacniho
argumentu (epsilon-vmackavani vrcholu).
- Voroneho diagram: definice, aplikace.
Prednaska 26.11. (JM)
- Souvislost Voroneho diagramu s polyedry,
maximalni kombinatoricka slozitost.
- Uvod do arrangementu.
Prednaska 3.12. (PV)
- tvrzeni o poctu bunek v arrangementu n nadrovin v obecne poloze v d-dimenzionalnim prostoru
- uroven bodu, uroven steny, hladina
- veta o hladinach, dukaz za pouziti nedokazaneho pravdepodobnostniho lemmatu
- zona nadroviny, veta o zone (zneni)
- dve pozorovani: veta o zone je asymptoticky optimalni, jednoduchy horni odhad je radove n na d
Prednaska 10.12. (JM)
- Dukaz vety o zone pro d=2. Dukaz pro vyssi dimenze
letos vynechame.
- Mnohocleny ve dvou promennych, stupen, nulova mnozina,
pomocna tvrzeni.
- Veta o sendvici (pripomenuti, bez dukazu). Polynomova veta o sendvici,
dukaz z vety o sendvici pomoci veronskeho zobrazeni.
Prednaska 17.12. (JM)
- Dukaz Szemerediho-Trotterovy vety (pro m=n)
pomoci polynomu; ucebni text zde.
- Uvod do geometrickych algoritmu, potize se zaokrouhlovanim a
pristupy k jejich prekonani.
- Strucne opakovani: inkrementalni algoritmus na konvexni obal v rovine.
- Konstrukce arrangementu primek - uvod (reprezentace arrangementu,
primocary algoritmus, ktery tridi pruseciky na kazde z primek).
Prednaska 7.1. (PV)
- Konvexne nezavisle mnoziny v R^d
- Erdos-Szekeresova veta: dva dukazy (z Remseyovek; pres salky a cepice)
- dolni odhad v Erdos-Szekeresove vete
Prednaska 14.1. (JM)
- Dokonceni algoritmu pro konstrukci arrangementu v rovine.
- Problem linearniho programovani, geometricky pohled na nej,
informace o nejdulezitejsich algoritmech.
- Seideluv algoritmus na linearni programovani v pevne
dimenzi, jeho analyza (indukci podle dimenze se dokaze, ze doba behu
je nejvys C_d.n, kde n je pocet poloprostoru).
TERMINY ZKOUSEK: Viz informace v zahlavi