ACM Summer School on Geometric Algorithms and their Applications (3-15 June, 2019)
ACM Summer School on Geometric Algorithms and their Applications (3-15 June, 2019)
Summer school webpage https://www.niser.ac.in/~aritra/ACM
Instructor Arijit Ghosh
Description A brief introduction to some topics in Convex geometry, Incidence Geometry, and Computational Geometry
Intended Audience Undergraduate students
References
[B19] J.-D. Boissonnat, F. Chazal and M. Yvinec, Geometric and Topological Inference, Cambridge University Press, 2018.
[K06] V. Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006.
[M02] J. Matoušek, Lectures on Discrete Geometry, Springer, 2002.
[D12] Z. Dvir, Incidence Theorems and Their Applications, Foundations and Trends in Theoretical Computer Science, 2012.
[S19] A. Sheffer, Incidence Theory with a Focus on the Polynomial Method, 2019.
Lecture details
Topics covered in Lectures 1 and 2
Introduction to affine independence (and dimension), convex combination, convex sets, and convex hulls
Results on convex geometry:
Radon's theorem
Helly's theorem
Carathéodory's theorem
Applications:
Centerpoint theorem
VC dimension of Halfspaces via Radon's theorem
Reading materials:
Link to video lectures:
Topics covered in Lecture 3 and 4
Introduction to planar graphs and crossing number
Crossing lemma
Introduction to point-line incidence bounds, unit distance problem, and distinct distance problem
Szemeredi-Trotter (ST) theorem, and proof of ST theorem via Crossing lemma
Applications ST Theorem:
Unit distance problem
Unit area triangle problem
Reading materials:
Link to video lectures
Topics covered in Lecture 5
Introduction to geometric and abstract simplicial complexes
Equivalence of geometric and abstract simplicial complexes
Introduction to Nerve and Nerve theorem (only statement)
Examples of simplicial complexes, e.g., Rips complex
Reading materials:
Chapter 2 of [B19]
Link to video lecture:
Topics covered in Lectures 6 and 7
Introduction to convex polytopes
Facial structure of convex polytopes
Convex polyhedra
Simplicial polytopes and simple convex polyhedra
Introduction to cell complexes
Point-hyperplane duality
Lower hulls and upper envelopes
Lower hulls and upper envelope duality
Statement of the asymptotic version of the Upper bound theorem
Reading materials:
Sections 3.1, 3.2 and 3.3 of [B19]
Link to video lectures:
Topics covered in Lectures 8 and 9
Lower envelopes and minimization diagrams
Voronoi diagrams
Delaunay complex as a nerve of Voronoi diagram
General position with respect to spheres
Delaunay triangulation theorem
Proof of the asymptotic version of the Upper bound theorem
Reading materials:
Link to lectures: