Zaklady kombinatoricke a vypocetni geometrie 2023/2024

(Jan Kyncl, Pavel Valtr, KAM)

Lecture: Wednesday at 12:20 in S9. The lectures are in English this year, but you can also ask questions in Czech or Slovak.
Prednaska: Ve stredu od 12:20 v S9. Prednaska je letos v anglictine, muzete se ale ptat i cesky nebo slovensky.

Exercise sessions: after the lecture at 14:00 in S8 according to the schedule on the exercise webpage.
Cviceni: po prednasce 14:00 v S8 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. Stranka 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

• [M1] 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.-8.11. (PV)

• Introductory information
• Basic notions: d-dimensional Euclidean space R^d (the set of d-tuples of real numbers), hyperplane, closed halfspace

Convexity

• Afinne subspace, afinne hull, afinne combination, afinne (in)dependence
• General position
• Convex set, convex hull, it is the set of all convex combinations
• Caratheodory's theorem (only statement, the proof is an exercise)
• Hyperplane separation theorem, sketch of proof of strict separation for a compact set vs. a closed set, and non-strict separation for arbitrary sets
• Helly's theorem
• Infinite version of Helly's theorem
• Centerpoint theorem
• The ham sandwich theorem (only statement)
• Center transversal theorem (only statement)

Incidence problems

• Geometric graph, crossing number of a geometric graph
• Crossing lemma (for geometric graphs)
• 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 (idea of one of the constructions)
• Upper bound O(n^{4/3}) on the number of unit distances (only statement & few words about the idea of the proof)
• Lower bound n^{1+c/(log log n)} on the number of unit distances (short description of the construction, no proof)

Lattices and Minkowski's theorem

• Minkowski's theorem for the integer lattice
• Application: looking out of a regular forest
• Lattice with basis z_1, z_2, ..., z_d, the determinant of a lattice
• Minkowski's theorem for general lattices (only few words about the proof - it can be found in [M1])
• 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 (only the statement)

Convex polytopes

• Geometric duality: duality transform D_0 between points (except 0) and hyperplanes avoiding the origin, duality lemma (duality preserves incidences), dual set X*
• Duality transform D between points and nonvertical hyperplanes
• Convex polytopes: V-polytope, H-polyhedron, H-polytope
• Basic examples: d-dimensional cube, crosspolytope and simplex
• Every H-polytope is a V-polytope
• Every V-polytope is a H-polytope

22.11. (JK)

• Face of a polytope P, facet, edge, vertex
• 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 of proof)
• Graph of a polytope, the graph of a 3-dimensional polytope is planar
• Euler's formula for 3-polytopes (only statement)

29.11. (JK)

• Balinski's theorem (only statement)
• Steinitz's theorem (only statement)
• Face lattice of a polytope and its properties (without proof), combinatorial equivalence of polytopes
• Corollary: the combinatorial type of a convex polytope is determined by the vertex-facet incidences (sketch of proof)
• 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)
• Remark about the graph of a 3-dimensional dual polytope
• 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

6.12. (JK)

• Moment curve, cyclic polytope, Gale's evenness criterion characterizing facets of the cyclic polytope
• 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)
• Voronoi diagram, regions (cells), faces; regions are convex polyhedra

13.12. (JK)

• Applications of Voronoi diagrams
• Delaunay triangulation (two definitions), properties without proofs
• Voronoi diagrams in R^d are projections of polyhedra in R^{d+1} (proof using hyperplanes tangent to the unit paraboloid)
• An asymptotic upper bound on the number of faces of all regions of the Voronoi diagram
• Power diagrams, their properties without proofs

20.12. (JK)

• Arrangement of hyperplanes in R^d, cells, faces
• Simple arrangement of hyperplanes, the exact number of cells of a simple arrangement of n hyperplanes (proof by double induction on n, d)
• Second proof for the exact number of cells of a simple arrangement of n hyperplanes (by induction on d)
• Arrangement of arbitrary subsets of R^d
• A zero set of a polynomial in d variables

3.1. (JK)

• Arrangement of zero sets of polynomials, Milnor–Thom theorem, asymptotic and more precise version (no proof)
• Sign patterns of a collection of polynomials
• Arrangement of pseudolines, wiring diagram, allowable sequence, isomorphic arrangements
• Stretchability of pseudoline arrangements, asymptotic numbers of pseudoline and line arrangements (using the Milnor–Thom theorem) imply that almost all pseudoline arrangements are not stretchable
• Remark about the algorithmic complexity of stretchability
• Pseudoarrangement of points as a dual of a pseudoline arrangement, order type, geometric realizations using integer coordinates may need exponentially many bits (without proof)

10.1. (JK)

• Number of vertices of level at most k in an arrangement of n hyperplanes, Clarkson's theorem on levels (statement), a construction showing that the upper bound is asymptotically tight
• Proof of Clarkson's theorem on levels for d=2 for simple arrangements
• The zone theorem, proof for facets and simple arrangements (in all dimensions)

Temata prednasek:

4.10.-8-11. (PV)

• Uvodni informace

Konvexita

• Afinni podprostor, afinni obal, afinni kombinace, afinni (ne)zavislost
• Konvexni mnozina, konvexni obal, je roven mnozine vsech konvexnich kombinaci
• Caratheodoryho veta (jen zneni, dukaz je jako cviceni)
• Veta o oddelovani nadrovinou, nastin dukazu ostreho oddeleni pro kompaktni vs. uzavrenou mnozinu a dukazu pro obecne mnoziny
• Afinni podprostor, afinni obal, afinni kombinace, afinni (ne)zavislost
• Hellyho veta
• Nekonecna verze Hellyho vety
• Veta o centru
• Veta o sendvici
• Center transversal theorem (jen zneni)

Incidence

• 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
• 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)

Mrizky a Minkowskeho veta

• Minkowskeho veta pro celociselnou mrizku
• Aplikace 1: 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

Konvexni polytopy

• 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
• Kazdy (omezeny) H-mnohosten je V-mnohostenem
• Kazdy V-mnohosten je H-mnohostenem

22.11. (JK)

• Stena mnohostenu, faseta, hrana, vrchol
• 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
• Eulerova formule pro 3-rozmerne mnohosteny (bez dukazu)

29.11. (JK)

• Balinskeho veta (bez dukazu)
• Steinitzova veta (bez dukazu)
• Svaz sten mnohostenu, jeho vlastnosti bez dukazu, kombinatoricka ekvivalence mnohostenu
• Dusledek: kombinatoricky typ mnohostenu je urceny incidencemi mezi vrcholy a fasetami (naznak dukazu)
• 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)
• Poznamka o grafu 3-rozmerneho dualniho mnohostenu
• Simplicialni mnohosten, jednoduchy mnohosten, priklady
• f-vektor mnohostenu, odhady na pocty sten 3-rozmerneho mnohostenu, definice "sousedskeho" mnohostenu

6.12. (JK)

• Momentova krivka, cyklicky mnohosten, Galeovo kriterium charakterizujici facety cyklickeho mnohostenu
• Presny pocet faset d-rozmerneho cyklickeho mnohostenu s n vrcholy
• Upper bound theorem (bez dukazu)
• Upper bound theorem - dukaz asymptoticke verze pro simplicialni mnohosteny
• Voroneho diagram, regiony (bunky), steny; regiony jsou konvexni polyedry

13.12. (JK)

• Aplikace Voroneho diagramu
• Delaunayova triangulace (dve definice), vlastnosti bez dukazu
• Voroneho diagramy v R^d jsou projekcemi polyedru v R^{d+1} (dukaz vyuzivajici tecne nadroviny k jednotkovemu paraboloidu)
• Asymptoticky horni odhad na celkovy pocet sten vsech regionu Voroneho diagramu
• Power diagramy, jejich vlastnosti bez dukazu

20.12. (JK)

• Arrangement nadrovin v R^d, bunky, steny
• Jendoduchy arrangement nadrovin, presny pocet bunek jednoducheho arrangementu n nadrovin v R^d (dukaz dvojitou indukci podle n, d)
• Druhy dukaz pro presny pocet bunek jednoducheho arrangementu n nadrovin v R^d (indukci podle d)
• Arrangement libovolnych podmnozin R^d
• Nulova mnozina polynomu v d promennych

3.1. (JK)

• Arrangement nulovych mnozin polynomu, Milnorova–Thomova veta, asymptoticka a presnejsi verze (bez dukazu)
• Znamenkove kombinace souboru polynomu
• Arrangement pseudoprimek, wiring diagram, "allowable" posloupnost, izomorfni arrangementy
• Narovnatelnost arrangementu pseudoprimek, asymptoticke pocty arrangementu pseudoprimek a primek (s pouzitim Milnorovy–Thomovy vety) implikuji, ze temer vsechny arrangementy pseudoprimek jsou nenarovnatelne
• Poznamka o algoritmicke slozitosti narovnatelnosti
• Pseudoarrangement bodu jako dual arrangementu pseudoprimek, order type, geometricka realizace pomoci celociselnych souradnic muze potrebovat exponencialni pocet bitu (bez dukazu)

10.1. (JK)

• Pocet vrcholu urovne nejvyse k v jednoduchem arrangementu n nadrovin, Clarksonova veta o hladinach, konstrukce ukazujici, ze horni odhad je asymptoticky tesny
• Dukaz Clarksonovy vety v dimenzi 2 pro jednoduche arrangementy, pravdepodobnostni metodou
• Veta o zone, dukaz pro fasety a jednoduche arrangementy (v rovine i ve vyssich dimenzich)