Informace k prednasce "Kombinatoricka a vypocetni geometrie I" 2014/2015
(Jiri Matousek, Martin Tancer, Pavel Valtr, KAM)
Prednaska: v pondeli od 14:00 v S4. Cviceni obcasna (viz stranka cviceni)
po prednasce tamtez.
Seznam odprednesene latky najdete na konci teto stranky.
Zde stránka cvičení
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. A
zde PDF soubor
mysleny pro ctecky a tablety.
- 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
Dosud probrana temata
Prednaska 6.10. (PV)
- Zakladni pojmy: d-dim. prostor R^d (= mn. usp. d-tic realnych cisel),
nadrovina, uzavr. poloprostor.
- Afinni podprostor, afinni obal, afinni kombinace,afinni nezavislost.
- Konvexni mnozina, konvexni obal, je roven mnozine vsech
konvexnich kombinaci (naznak dukazu).
- Oddelovaci veta, postup dukazu ze disjunktni kompaktni konvexni
mnoziny lze ostre oddelit.
- Caratheodoryho veta, Radonova veta - zatim jen zneni.
- na cviceni zadan domaci ukol c. 1 (viz
www stranku cviceni).
Prednaska 13.10. 14:00 (PV)
- Radonova veta (s dukazem)
- Hellyho veta
- Nekonecna verze Hellyho vety
- veta o centru
Prednaska 13.10. 15:40 (PV)
- Lemma o prusecikovem cisle (crossing lemma)
- Szemerediho-Trotterova veta o maximalnim poctu incidenci bodu a primek
- Horni odhad na pocet primek obsahujich alespon k bodu n-bodove mnoziny
- Horni odhad O(n^{4/3}) pro pocet jednotkovych vzdalenosti
- Zminky o dolnich odhadech u vyse uvedenych tri hornich odhadu
Prednaska 20.10. (PV)
- Minkowskeho veta
- veta o sendvici
- veta o centralni transversale (spolecne zobecneni vety o centru a vety o sendvici)
Přednáška 27.10. (MT)
-
Opakování duality: duál bodu k nadrovině, duální množina.
-
Mnohostěny: H-mnohostěny a V-mnohostěny a jejich ekvivalence. Krychle, simplex, křížový mnohostěn.
- Stěny mnohostěnů, vrcholy, hrany, facety, extremální body. Mnohostěn je konvexním obalem svých vrcholů a stěna stěny je stěna (zatím jen znění).
Přednáška 3. 11. (MT)
- Důkaz, že mnohostěn je konvexním obalem svých vrcholů a stěna stěny je stěna.
- Graf mnohostěnu: Steinitzova věta (graf je rovinný a 3-souvislý, právě když je izomorfní grafu nějakého 3-rozměrného mnohostěnu), zmínka o Balinského větě (graf k-rozměrného mnohostěnu je k-souvislý). Obě věty bez důkazu.
- Svaz stěn mnohostěnu: existence průseků a spojení, svaz je gradovaný, atomický a koatomický. Je jednoznačně určený incidencemi mezi vrcholy a facetami.
- Duální mnohostěn: stěny duálního mnohostěnu jsou v bijekci se stěnami původního (bez důkazu).
Přednáška 10. 11. (MT)
- Simpliciální a jednoduché mnohostěny. Poznámka o pravidelných mnohostěnech.
- Počet stěn mnohostěnů: f-vektor, f-vektory v dimenzi 2 a 3.
- Cyklický mnohostěn: momentová křivka, nadroviny protínající momentovou křivku a afinní nezávislost d bodů na momentové křivce. Galeho kritérium sudosti. Počet facet cyklického mnohostěnu (poznámka o počtu k-stěn a Dehn Sommervilleových rovnostech).
Přednáška 24. 11. (MT)
- Upper bound theorem (bez důkazu). Asymptotická verze s důkazem (nejprve pro simpliciální mnohostěny a potom obecně).
- Voronoiovy diagramy: region je konvexní polyédr. Příklady aplikací (poštovní problém, interpolace funkcí).
- Jednotkový paraboloid. Voronoiův diagram konečné množiny bodů je projekcí facet jistého polyédru.
Přednáška 1. 12. (MT)
- Odhad na počet všech stěn Voronoiova diagramu.
- Arrangement přímek v rovině a nadrovin v d-rozměrném prostoru. Odhad na počet buněk takového arrangementu.
- Arrangement obecného souboru množin.
- Arrangement nulových množin polynomů. Znaménkový vzorek souboru polynomů. Milnor-Thomova věta (bez důkazu).
Přednáška 8. 12. (MT)
- Arrangementy pseudopřímek. Narovnatelnost arrangementu pseudopřímek. Většina (jednoduchých) arrangementů pseudopřímek není narovnatelných (jako aplikace Milnor-Thomovy věty).
- Počet vrcholů na úrovni k arrangementu nadrovin v d-rozměrném prostoru. Clarksonova věta o úrovních. (Náznak důkazu, že odhad v Clarksonově větě je těsný; důkaz věty přístě - ve speciálním případě.)
Přednáška 15. 12. (PV)
- Dukaz vety o urovnich (= veta o hladinach)
- Jednoduche odhady na slozitost zony nadroviny: dolni radove n na (d-1), horni radove n na d
- veta o zone nadroviny, dukaz proveden pouze v rovine (ve vyssich dimenzich by se delal indukci podle d)
Přednáška 5.1. (PV)
- zminka o algoritmu na vypocet konvexniho obalu n bodu v rovine v case O(nlogn)
- zminka o "output-sensive" algoritmech na vypocet konvexniho obalu n bodu v rovine v case O(nlogh), kde h je pocet hran vysledneho konvexniho obalu
- Motivace k problemu lokalizace bodu v lichobeznikove dekompozici n neprotinajicich se usecek (pocitacova grafika, pocitacove hry, architektura apod.)
- Lichobeznikova dekompozice a vypocet prumerne slozitosti lokalizace bodu (za pouziti lichobeznikovych dekompozic pri postupnem pridavani usecek v nahodnem poradi), rovnez horni odhady na stredni hodnotu velikosti pameti a casu pri budovani lich. dekompozice