Zaklady kombinatoricke a vypocetni geometrie 2020/2021

Distancni vyuka:

Prednaska: v utery od 9:00 "v S5".

Cviceni: po prednasce 10:40 "v S5" podle rozvrhu na strance 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 apod.). O naplni prednasky si muzete udelat lepsi predstavu podle latky probirane v minulych letech.

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).
• Chanuv algoritmus pro konstrukci konvexniho obalu: doi:10.1007/BF02712873
• Kapitola "Geometricke algoritmy" ve skriptech Martina Marese
• 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

Temata prednasek:

29.9. (JK)

• Uvodni informace
• Zakladni pojmy: d-rozmerny euklidovsky prostor R^d (mnozina usporadanych d-tic realnych cisel), nadrovina, uzavreny poloprostor
• Afinni podprostor, afinni obal, afinni kombinace, afinni (ne)zavislost
• Konvexni mnozina, konvexni obal, je roven mnozine vsech konvexnich kombinaci (naznak dukazu)
• Caratheodoryho veta (jen zneni, dukaz je jako cviceni)
• Veta o oddelovani nadrovinou, naznak dukazu, ze disjunktni kompaktni konvexni mnoziny lze ostre oddelit, myslenka pro pripad omezenych mnozin

6.10. (JK)

• Radonova veta
• Hellyho veta
• Nekonecna verze Hellyho vety
• Veta o centru

13.10. (JK)

• Veta o sendvici (jen zneni)
• Center transversal theorem (jen zneni)
• Nakresleni grafu, prusecikove cislo grafu
• Prusecikove lemma

20.10. (JK)

• Szemerediova–Trotterova veta o maximalnim poctu incidenci bodu a primek
• Dolni odhad na pocet incidenci n bodu a n primek
• Horni odhad O(n^{4/3}) na pocet jednotkovych vzdalenosti (jen zneni)
• Dolni odhad n^{1+c/(log log n)} na pocet jednotkovych vzdalenosti (popis konstrukce, bez dukazu)
• Minkowskeho veta pro celociselnou mrizku

27.10. (JK)

• Aplikace Minkowskeho vety: vyhlizeni z pravidelneho lesika
• Aplikace 2: diofanticka aproximace realnych cisel
• Obecna mrizka s bazi z_1, z_2, ..., z_d, determinant mrizky
• Minkowskeho veta pro obecnou mrizku (jen zneni)
• Aplikace obecne Minkowskeho vety: kazde prvocislo tvaru 4k+1 je souctem dvou ctvercu
• Geometricka dualita: D_0 mezi body (krome 0) a nadrovinami neobsahujicimi pocatek, dualni mnozina X*

3.11. (JK)

• Dualita mezi body a nesvislymi nadrovinami
• Konvexni mnohosteny: V-mnohosten, H-polyedr (H-mnohosten), H-polytop, dimenze mnohostenu
• Zakladni priklady: d-rozmerna krychle, d-rozmerny krizovy mnohosten, simplex
• Kazdy H-polytop (omezeny H-mnohosten) je V-mnohostenem
• Kazdy V-mnohosten je H-mnohostenem (naznak dukazu s pouzitim duality a obracene implikace)
• Stena mnohostenu, faseta, hrana, vrchol

10.11. (JK)

• Extremalni bod mnoziny
• Extremalni body mnohostenu P jsou presne jeho vrcholy, P je konvexni obal svych vrcholu
• Vrcholy steny F mnohostenu P jsou presne ty vrcholy P lezici v F
• Steny steny F mnohostenu P jsou presne ty steny P lezici v F (cast dukazu jen naznacena)
• Graf mnohostenu, graf 3-rozmerneho mnohostenu je rovinny
• Balinskeho veta (bez dukazu)
• Steinitzova veta (bez dukazu)
• Svaz sten mnohostenu: definice + prusek a spojeni, kombinatoricka ekvivalence mnohostenu
• Vlastnosti svazu sten (bez dukazu)
• Kombinatoricky typ mnohostenu urcen incidencemi mezi vrcholy a fasetami (naznak dukazu)

24.11. (PV)

• Dualni mnohosten
• Svaz sten mnohostenu
• Svaz sten dualniho mnohostenu je "prevracenim" svazu sten puvodniho mnohostenu a j-rozmermne steny P odpovidaji (d-1-j)-rozmernym stenam P* (priklady, naznak dukazu)
• Simplicialni mnohosten, jednoduchy mnohosten, priklady, pojmy jsou navzajem dualni
• f-vektor mnohostenu, odhady na pocty sten 2- a 3-rozmerneho mnohostenu
• Momentova krivka, cyklicky mnohosten, prunik momentove krivky s nadrovinou, Galeovo kriterium charakterizujici facety cyklickeho mnohostenu

1.12. (PV)

• Presny pocet facet d-rozmerneho cyklickeho mnohostenu s n vrcholy
• Upper bound theorem (bez dukazu)
• Asymptoticka verze upper bound theoremu (s dukazem).
• Region bodu a Voroneho diagram.
• Motivace pro Voroneho diagramy: nejblizsi studna/posta.
• Vztah mezi V. diagramy v dim d a konv. mnohosteny v dim d+1: jednotkovy paraboloid a lemma o jeho tecnych nadrovinach (dokonceni priste).

8.12. (PV)

• Horni odhad slozitosti Vor. diagramu (pomoci projekce vhodneho polyedru)
• Arrangementy nadrovin v R^d (uvod)

15.12. (PV)

• Arrangementy nadrovin v R^d, pocet bunek (a vrcholu) jednoducheho arrangementu n nadrovin v R^d
• Hladina vrcholu v jednoduchem arrangementu primek.
• Clarksonova veta o hladinach.
• Zduvodneni ze je tesna. Dukaz v dimenzi 2 pomoci pravdepodobnostniho pristupu.

22.12. (PV)

• Zona nadroviny. Veta o zone (dukaz pro dim 2, zacatek dukazu pro (d-1)-steny v lib. dimenzi)

5.1. (PV)

• dokonceni dukazu vety o zone v libovolne dimenzi: dokonceni dukazu pro (d-1)-steny (fasety), pote pro steny dimenzi >1, nakonec pro 0,1-steny (bez detailu pro 0-steny)

Topics covered:

29.9. (JK)

• Introductory information
• Basic notions: d-dimensional Euclidean space R^d (the set of d-tuples of real numbers), hyperplane, closed halfspace
• Afinne subspace, afinne hull, afinne combination, afinne (in)dependence
• Convex set, convex hull, it is the set of all convex combinations (sketch of proof)
• Caratheodory's theorem (only statement, the proof is an exercise)
• Hyperplane separation theorem, sketch of proof for the case of two compact sets, idea for the case of bounded sets

6.10. (JK)

• Radon's theorem
• Helly's theorem
• Infinite version of Helly's theorem
• Existence of a centerpoint

13.10. (JK)

• The ham sandwich theorem (only statement)
• Center transversal theorem (only statement)
• Drawing of a graph, crossing number of a graph
• Crossing lemma

20.10. (JK)

• Szemeredi–Trotter theorem about maximum number of incidences between points and lines
• Lower bound on the number of incidences between n points and n lines
• Upper bound O(n^{4/3}) on the number of unit distances (only statement)
• Lower bound n^{1+c/(log log n)} on the number of unit distances (description of the construction, no proof)
• Minkowski's theorem for the integer lattice

27.10. (JK)

• Application of Minkowski's theorem: looking out of a regular forest
• Application 2: Diophantine approximation of real numbers
• Lattice with basis z_1, z_2, ..., z_d, the determinant of a lattice
• Minkowski's theorem for general lattices (only statement)
• An application of the general Minkowski's theorem in number theory: each prime number of the form 4k + 1 can be written as a sum of two squares.
• Geometric duality: duality transform D_0 between points (except 0) and hyperplanes avoiding the origin, dual set X*

3.11. (JK)

• Duality transform D between points and nonvertical hyperplanes
• Convex polytopes: V-polytope, H-polyhedron, H-polytope, dimension of a polytope
• Basic examples: d-dimensional cube, crosspolytope and simplex
• Every H-polytope is a V-polytope
• Every V-polytope is a H-polytope (sketch of a proof using duality and reverse implication)
• Face of a polytope P, facet, edge, vertex

10.11. (JK)

• Extremal point of a set
• The extremal points of P are exactly its vertices, P is the convex hull of its vertices
• The vertices of a face F of P are exactly those vertices of P that lie in F
• The faces of a face F of P are exactly those faces of P that lie in F
• Graph of a polytope, the graph of a 3-dimensional polytope is planar
• Balinski's theorem (only statement)
• Steinitz's theorem (only statement)
• Face lattice of a polytope, meets and joins, combinatorial equivalence of polytopes
• Properties of the face lattice (without proof)
• Corollary: the combinatorial type of a convex polytope is determined by the vertex-facet incidences (sketch of proof)