Combinatorial and Computational Geometry I 2018/2019
Kombinatoricka a vypocetni geometrie I 2018/2019
(Jan Kyncl, Martin Tancer, KAM)
Lecture: Thursdays at 14:00 in S9.
Prednaska: ve ctvrtek od 14:00 v S9.
Exercise sessions: after the lecture at 15:40 in S6 according to the schedule on the
exercise webpage.
Cviceni: po prednasce 15:40 v S6 podle rozvrhu na
strance cviceni.
Extent of teaching: WINTER semester 2/2 (Exam and Exercise credit). Entry in SIS, syllabus
Rozsah vyuky: ZIMNI semestr 2/2 Z, Zk. Záznam v SISu, sylabus
Annotation
Discrete geometry investigates combinatorial properties of geometric objects such as finite point sets or convex sets in Euclidean spaces. Computational geometry considers the design of efficient algorithms for computing with geometric configurations, and discrete geometry serves as its mathematical foundation. Part I of the course is a concise introduction.
The lecture will be very similar to the last year.
The contents of Part II varies among the years, each year covering a few selected topics in more depth.
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.
Literature
-
Jiri Matousek's lecture notes Introduction to Discrete Geometry, ITI Series 2003-150, available in the Computer Science library of MFF UK.
Here is a postscript file with two pages of text on one A4 page, intended for printing.
Here is a PDF file for readers and tablets.
- The lecture notes are, in fact, a selection of topics from the book J. Matousek: Lectures on Discrete Geometry.
- A text for the part about incremental geometric algorithms is available
here
(12 pages).
- Chan's algorithm for the construction of the convex hull: doi:10.1007/BF02712873
- A standard introductory text about computational geometry:
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf: Computational
Geometry: Algorithms and Applications, Springer-Verlag, Berlin, 1997.
The computer science library of MFF UK has a few copies.
-
J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press
1995
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
Topics covered:
4.10. (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, almost full proof for the case of two compact sets, idea for the case of bounded sets
11.10. (JK)
- Radon's theorem
- Helly's theorem
- Infinite version of Helly's theorem
- Existence of a centerpoint
- The ham sandwich theorem (only statement)
18.10. (JK)
- Center transversal theorem (only statement)
- Drawing of a graph, crossing number of a graph
- Crossing lemma
- Szemeredi–Trotter theorem about incidences between points and lines
- Lower bound on the number of incidences between n points and n lines
25.10. (MT)
- It seems that there are no non-Czech students attending the lecture anymore. Thus I stopped writing down the topics in English (you still can find them in Czech below). English version can be added on a request.
1.11. (JK)
- Geometric duality: duality transform D_0 between points (except 0) and hyperplanes avoiding the origin, dual set X*, 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)
8.11. (JK)
- Face of a polytope P, facet, edge, vertex, every face is a convex polytope
- 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 (sketch)
- Graph of a polytope, the graph of a 3-dimensional polytope is planar
- Balinski's theorem (only statement)
- Steinitz's theorem (only statement)
15.11. (JK)
- Face lattice of a polytope and its properties (without proof), combinatorial equivalence of polytopes
- Dual polytope P*, the face lattice of a dual polytope is "upside down" and j-faces of P correspond to (d-1-j)-faces of P* (without proof)
- Simplicial polytope, simple polytope, examples
- The f-vector of a polytope, estimates on the number of faces of 3-dimensional polytopes, definition of neighborly polytopes
- Moment curve, cyclic polytope, Gale's evenness criterion characterizing facets of the cyclic polytope (proof postponed)
29.11. (JK, MT)
- Proof of Gale's criterion
- Exact number of facets of the d-dimensional cyclic polytope with n vertices
- The upper bound theorem (only statement)
- An asymptotic version of the upper bound theorem (proof only for simplicial polytopes)
- ...
Temata prednasek:
4.10. (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
11.10. (JK)
- Radonova veta
- Hellyho veta
- Nekonecna verze Hellyho vety
- Veta o centru
- Veta o sendvici (jen zneni)
18.10. (JK)
- Center transversal theorem (jen zneni)
- Nakresleni grafu, prusecikove cislo grafu
- Prusecikove lemma
- Szemerediova–Trotterova veta o maximalnim poctu incidenci bodu a primek
- Dolni odhad na pocet incidenci n bodu a n primek
25.10. (MT)
- Minkowského věta pro celočíselnou mřížku
- Aplikace Minkowského věty: lesík
- Obecná mřížka, její determinant, Minkowského věta pro obecnou mřížku
- Aplikace obecnější verze: provočíslo, které dává zbytek 1 při dělení 4 je součtem dvou čtverců
1.11. (JK)
- Geometricka dualita: D_0 mezi body (krome 0) a nadrovinami neobsahujicimi pocatek, dualni mnozina X*, dualita mezi body a nesvislymi nadrovinami
- Konvexni mnohosteny: V-mnohosten, H-mnohosten, H-polytop, dimenze mnohostenu
- Zakladni priklady: d-rozmerna krychle, d-rozmerny krizovy mnohosten, simplex
- Kazdy omezeny H-mnohosten je V-mnohostenem
- Kazdy V-mnohosten je H-mnohostenem (naznak dukazu s pouzitim duality)
8.11. (JK)
- Stena mnohostenu, faseta, hrana, vrchol, kazda stena je konvexni mnohosten
- 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 (naznak dukazu)
- Graf mnohostenu, graf 3-rozmerneho mnohostenu je rovinny
- Balinskeho veta (bez dukazu)
- Steinitzova veta (bez dukazu)
15.11. (JK)
- Svaz sten mnohostenu a jeho vlastnosti (bez dukazu), kombinatoricka ekvivalence mnohostenu
- Dualni mnohosten P*
- Svaz sten dualniho mnohostenu je "prevracenim" svazu sten puvodniho mnohostenu a j-rozmermne steny P odpovidaji (d-1-j)-rozmernym stenam P* (bez dukazu)
- Simplicialni mnohosten, jednoduchy mnohosten, priklady
- f-vektor mnohostenu, odhady na pocty sten 3-rozmerneho mnohostenu, definice "sousedskeho" mnohostenu
- Momentova krivka, cyklicky mnohosten, Galeovo kriterium charakterizujici fasety cyklickeho mnohostenu (dukaz odlozen)
29.11. (JK, MT)
- Dukaz Galeova kriteria
- Presny pocet faset d-rozmerneho cyklickeho mnohostenu s n vrcholy
- Veta o hornim odhadu na pocet sten d-rozmerneho mnohostenu s n vrcholy (bez dukazu)
- Asymptoticka verze vety o hornim odhadu, dukaz pro simplicialni mnohosteny
- Region bodu, Voroného diagram.
- Jednotkový paraboloid, jeho tečné nadroviny a polyédr jimi určený pro množinu bodů v Rd.
- Voroného diagram je projekcí faset onoho polyédru. Důsledek: asymptotický odhad počtu stěn všech regionů Voroného digramu.
6.12. (MT)
- Arrangement nadrovin; buňky, k-stěny
- Pozorování o počtu vrcholů v jednoduchém arrangementu nadrovin. Tvrzení o počtu buněk.
- Arrangement obecných množin a jeho stěny.
- Arrangement nulových množin polynomů. Znaménkové vzory. Milnor-Thomova věta.
13.12. (MT)
- Arrangementy pseudopřímek. Kódování arrangementu. Narovnatelnost. Příklad nejednoduchého arrangementu, který není narovnatelný.
- Většina jednoduchých arrangementů pseudopřímek není narovnatelná (pomocí Milnor-Thomovy věty).
- Hladina bodu v arrangementu nadrovin.
- Clarksonova věta o hladinách. (Důkaz pouze v rovině pro jednoduché arrangementy v obecné poloze.)
20.12. (MT)
- Věta o zóně. Pozorování, že důkaz je snadný pro buňky v jednoduchém arrangementu.
- Důkaz pro jednoduché arrangementy v rovině. Ve vyšší dimenzi pouze pro (d-1)-stěny v jednoduchém arrangementu.
3. 1. (MT)
- Geometrické algoritmy. Naivní a inkrementální algoritmus pro konstrukci (jednoduchého) arrangementu přímek v rovině
(naivní v čase O(n2 log n), inkrementální v čase O(n2)).
- Inkrementální algoritmus pro konstrukci konvexního obalu množiny bodů v rovině v čase
O(n log n).
- Chanův algoritmus pro konstrukci konvexního obalu množiny bodů v rovině, senzitivní vzhledem k výstupu, v čase
O(n log h), kde h je počet vrcholů konvexního obalu. (Krok s binárním prohledáváním v důkazu pouze naznačen, ostatní kroky byly pořádně.)
10. 1. (MT)
- Problém lokalizace bodu - motivace.
- Lichoběžníková dekompozice a problém lokalizace bodu v lichoběžníkové dekompozici.
- Konstrukce datové struktury, kde je lokalizace možná v čase O(log n). Konstrukce zabere čas O(n log n) a místo O(n), pro místo pouze náznak.