Introduction to Combinatorial and Computational Geometry 2025/2026

Zaklady kombinatoricke a vypocetni geometrie 2025/2026

Lecture: Friday at 10:40 in S3. The lectures are in English this year, but you can also ask questions in Czech or Slovak.
Prednaska: V patek od 10:40 v S3. Prednaska je letos v anglictine, muzete se ale ptat i cesky nebo slovensky.

Exercise sessions: after the lecture at 12:20 in S8 according to the schedule on the exercise webpage.
Cviceni: po prednasce 12:20 v S8 podle rozvrhu na strance cviceni.

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:

3.10. (MT)

• Introductory information
• Basic notions: we work in d-dimensional Euclidean space R^d which is in particular a linear space thus we can use notions form linear algebra
• Afinne subspace, afinne hull, afinne combination, afinne (in)dependence
• Hyperplane and halfspace
• 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 (statement)

10.10. (JK)

• Hyperplane separation theorem: sketch of proof for the case of two compact sets, idea for the case of bounded sets
• Radon's theorem
• Helly's theorem
• Infinite version of Helly's theorem
• Existence of a centerpoint

17.10. (JK)

• The ham sandwich theorem (only statement)
• Center transversal theorem (only statement)
• Drawing of a graph, crossing number of a graph
• Crossing lemma
• Incidences between points and lines, examples
• Statement of Szemeredi–Trotter theorem

24.10. (JK)

• Lower bound on the number of incidences between n points and n lines
• Szemeredi–Trotter theorem about maximum number of incidences between points and 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
• Application of Minkowski's theorem: looking out of a regular forest

31.10. (JK)

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

Temata prednasek:

10.10. (JK)

• Veta o oddelovani nadrovinou: naznak dukazu, ze disjunktni kompaktni konvexni mnoziny lze ostre oddelit, myslenka pro pripad omezenych mnozin
• Radonova veta
• Hellyho veta
• Nekonecna verze Hellyho vety
• Veta o centru

17.10. (JK)

• Veta o sendvici (jen zneni)
• Center transversal theorem (jen zneni)
• Nakresleni grafu, prusecikove cislo grafu
• Prusecikove lemma
• Incidence mezi body a primkami, priklady
• Zneni Szemerediovy–Trotterovy vety

24.10. (JK)

• Dolni odhad na pocet incidenci n bodu a n primek
• Szemerediova–Trotterova veta o maximalnim poctu incidenci bodu a 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
• Aplikace Minkowskeho vety: vyhlizeni z pravidelneho lesika

31.10. (JK)

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