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í

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