Introduction to Combinatorial and Computational Geometry 2021/2022
Zaklady kombinatoricke a vypocetni geometrie 2021/2022
(Jan Kyncl, Martin Tancer, KAM)
Lecture: Wednesday at 15:40 in S9.
Prednaska: Ve stredu od 15:40 v S9.
Exercise sessions: after the lecture at 17:20 in S9 according to the schedule on the
exercise webpage.
Cviceni: po prednasce 17:20 v S9 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. Zaznam v SISu, sylabus
For questions on zoom streaming/recording of lectures 28, please send an email to Martin Tancer. Unfortunately, the lecture 2 has not been streamed/recorded and it is not clear how it will be with the other lectures.
The first lecture and lectures 913 are going to be streamed over zoom and recorded. The access will be shared with students registered in SIS. This is a backup option for those who cannot attend in person for serious reason.
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. jeli 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 2003150, 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, SpringerVerlag, 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 2003150 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, SpringerVerlag, Berlin, 1997.
Informaticke oddeleni knihovny ma nekolik exemplaru.

J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press
1995
Topics covered:
29. 9. (JK)
 Introductory information
 Basic notions: ddimensional Euclidean space R^d (the set of dtuples 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. (MT), Literature: [M1, 1.3 + 1.4]
 Radon's theorem
 Helly's theorem
 Infinite version of Helly's theorem
 Existence of a centerpoint
13. 10. (MT), Literature: [M1, 1.4 + 4.1 + 4.3]
 The ham sandwich theorem (only statement)
 Center transversal theorem (only statement)
 Drawing of a graph, crossing number of a graph
 Crossing lemma
 Szemeredi–Trotter theorem about maximum number of incidences between points and lines
20.10. (MT), Literature: [M1, 4.1 + 4.2 + 2.1]
 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
 Application 1: looking out of a regular forest
 Application 2: Diophantine approximation of real numbers
27.10. (MT), Literature: [M1, 2.2, 5.1, 5.2]
 Lattice with basis z_1, z_2, ..., z_d, the determinant of a lattice
 Minkowski's theorem for general lattices (proof modulo properties of the volume)
 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, duality lemma (duality preserves incidences), dual set X*
 Convex polytopes: Vpolytope, Hpolyhedron, Hpolytope
 Vpolytopes and Hpolytopes coincide (statement only for now)
 Basic examples: ddimensional cube, crosspolytope and simplex
3.11. (MT), Literature: [M1, 5.2, 5.3]
 Every Hpolytope is a Vpolytope
 Every Vpolytope is an Hpolytope (sketch of a proof using duality and reverse implication)
 Dimension of a polytope
 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 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 3dimensional polytope is planar
 Balinski's theorem (only statement)
 Steinitz's theorem (only statement)
10.11. (MT), Literature: [M1, 5.3, 5.4]
 Faces of a crosspolytope and of a cube.
 Face lattice of a polytope, meets and joins, combinatorial equivalence of polytopes, graded, atomic and coatomic (sketched only)
 Remark on efficient representation of the face lattice in a computer
 Face lattice of the dual polytope is the inverse of the face lattice of the primal polytope. (In particular, jfaces of P correspond to (d1j)faces of P*.)
 Simplicial and simple polytope, examples, the terms are mutually dual.
 fvector of a polytope, bounds on the number of faces of a 3polytope
 Moment curve, intersection of the moment curve with a hyperplane
22.11. (MT), Literature: [M1, 5.4, 5.5]
 Cyclic polytope, Gale's criterion describing facets of the cyclic polytope
 Exact number of low dimensional faces of the cyclic dpolytope with n vertices
 Exact number of facets of the cyclic dpolytope with n vertices
 Remark on DehnSommerville equalities (without proof)
 Upper bound theorem (without proof)
 Asymptotic upper bound theorem (with proof), simplicialni polytopes first, then all.
1.12. (JK)
 Voronoi diagram, regions (cells), faces
 Delaunay triangulation, properties without proofs
 Unit paraboloid, definition of hyperplanes e(p) tangent to the unit paraboloid
 Voronoi diagrams in R^d are projections of polyhedra in R^{d+1}
 An asymptotic upper bound on the number of faces of all regions of the Voronoi diagram
 Power diagrams, their properties without proofs
8.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
15.12. (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
 Remarks about the algorithmic complexity of stretchability
22.12. (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)
5.1. (JK)
 Algorithm for a construction of the arrangement of n lines in the plane: straightforward with running time O(n^2 log n), incremental with running time O(n^2)
 Incremental algorithm for the convex hull of n points in the plane with running time O(n log n)
 Chan's outputsensitive algorithm for the convex hull with running time O(n log h) where h is the number of vertices of the convex hull