Combinatorial Geometry (M.Tech CS, 2 Year, 2020-21)
Combinatorial Geometry (M.Tech CS, 2 Year, 2020-21)
Instructor Arijit Bishu and Arijit Ghosh
Teaching assistant Soumi Nandi
Description To study the basics of Combinatorial Geometry.
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences.
Class timings Tuesday 10:30 - 12:25 hrs, and Wednesday 16:10 - 18:05 hrs.
References
[AS16] Noga Alon and Joel Spencer, The Probabilistic Method, 4th Edition, Wiley, 2016.
[AZ14] Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK, Springer, 2014.
[B+08] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer Verlag, 2008.
[BCY18] Jean-Daniel Boissonnat, Frédéric Chazal, and Mariette Yvinec, Geometric and Topological Inference, Cambridge Texts in Applied Mathematics, 2018.
[BHK20] Avrim Blum, John Hopcroft, and Ravindran Kannan, Foundations of Data Science, Cambridge University Press, 2020.
[BO97] Imre Barany and Shmuel Onn, Caratheodory's Theorem: Colourful and Applicable, Bolyai Society Mathematical Studies, 6:11 - 21, 1997.
[E97] György Elekes, On the number of sums and products, Acta Arithmetica, (81):365–367, 1997.
[GH12] Bernd Gärtner and Michael Hoffmann, Computational Geometry, Lecture Notes, ETH, 2012.
[H11] Sariel Har-Peled, Geometric Approximation Algorithms, American Mathematical Society, 2011.
[K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006.
[LGM19] Jesus de Loera, Xavier Goaoc, Frederic Meunier and Nabil H. Mustafa, The Discrete Yet Ubiquitous Theorems of Caratheodory, Helly, Sperner, Tucker, and Tverberg, Bulletin of the American Mathematical Society, 56: 415-511, 2019.
[M16] David M. Mount, Lecture Notes on Computational Geometry, Department of Computer Science, University of Maryland, 2016.
[M94] Ketan Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice Hall, 1994.
[M99] Jiri Matousek, Geometric Discrepancy, Springer, 1999.
[M02] Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002.
[MU05] Michael Mitzenmacher and Eli Upfal, Probability and Computing, Cambridge University Press, 2005.
[MR95] Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
[PA95] Janos Pach and Pankaj K Agarwal, Combinatorial Geometry, Wiley-Interscience, 1995.
[RV21] Tim Roughgarden and Gregory Valiant, The Modern Algorithmic Toolbox, Lecture Notes, Stanford University, 2021.
[SA00] Micha Sharir and Pankaj K Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 2000.
[S93] Rolf Schneider, Convex Bodies: The Brunn-Minkowski Theory, Cambridge University Press, 1993.
[U15] Torsten Ueckerdt, Combinatorics in the Plane, Lecture Notes, KIT, 2015.
[WS11] David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
[Z95] Günter M. Ziegler, Lectures on Polytopes, Springer-Verlag, 1995.
Lecture details
Topics covered in Lecture 1 (28 Jan'21)
Introduction to Combinatorial Geometry
Incidence geometry, and statement of Szemerédi–Trotter Theorem
Weaker bound on point-line incidence bound using Kővári–Sós–Turán Theorem
Affine space, affine dependence, and affine hull
Convex combination, and convex hull
Basic properties of convex hulls
Reading materials:
Topics covered in Lecture 2 (2 Feb'21)
Revisiting affine dependence, and convex hull
Radon's Theorem
Helly's Theorem
Carathéodory's Theorem
Reading materials:
Topics covered in Lecture 3 (4 Feb'21)
Open, closed, bounded, compact sets in Euclidean Space
The infinite version of Helly's Theorem
Why "infinite version" of Helly's Theorem is tight
Definition of Center Point
Rado's Center Point Theorem
Conditions for approximating a function by an affine function
Reading materials:
Topics covered in Lecture 4 (9 Feb'21)
Rey-Pastór-Santaló Theorem on Common Transversal of Segments
Conditions for approximating a function by an affine function
Jung' Theorem
Reading materials:
Topics covered in Lecture 5 (11 Feb'21)
Revisiting Jung's Theorem
Kirschberger’s Theorem on Separating Sets
Klee’s Theorems on Covering/Intersecting/Hitting by Translates
Reading materials:
Topics covered in Lecture 6 (17 Feb'21)
Convex hull, Voronoi diagram, and Delaunay triangulation
Connecting convex hull to Delaunay triangulation via lifting map
Graham's scan algorithm for computing convex hull
Jarvis March's algorithm for computing convex hull
Chan's output-sensitive convex hull algorithm
Reading materials:
Lectures 3 and 4 in [M16]
Topics covered in Lecture 7 (23 Feb'21)
Introduction to Randomized Incremental Construction (RIC)
Convex hull via RIC
Voronoi diagrams - definition and basic properties
(Algorithm for computing Voronoi diagram not included in the course)
Reading materials:
Topics covered in Lecture 8 (24 Feb'21)
Delaunay triangulation - dual of Voronoi diagram, circumcircle, and Delaunay triangle
(Algorithm for constructing Delaunay triangulation not included in the course)
Minimum Spanning tree (MST) for a point set
Maximizing angles and edge flipping
Lifting Transform (connecting Convex hull, Delaunay triangulation, and Voronoi diagram)
Reading materials:
Topics covered in Lecture 9 (2 March'21)
Some applications of the Voronoi diagram
Zone theorem
Polygon triangulation and diagonals; art gallery theorem
Reading materials:
Lectures 14 and 22 in [M16]
Topics covered in Lecture 10 (3 March'21)
Erdos-Szekeres theorem
Sylvester-Gallai theorem
Crossing lemma
Point line incidence, and Szemerédi–Trotter theorem
Reading materials:
Chapters 1 and 2 in [U15]
Topics covered in Lecture 11 (4 March'21)
Proof of Crossing Lemma
Proof of Szemerédi–Trotter theorem
Reading materials:
Topics covered in Lecture 12 (23 March'21)
Szemerédi–Trotter theorem for heavy lines
Sum-product estimates in additive combinatorics
Reading materials:
Topics covered in Lecture 13 (25 March'21)
Topics covered in Lecture 14 (26 March'21)
Topics covered in Lecture 15 (30 March'21)
Topics covered in Lecture 16 (1 April'21)
Duality of points and lines
Reading materials:
Lectures 7 and 15 in [M16]
Topics covered in Lecture 17 (8 April'21)
Borsuk Ulam theorem
Ham Sandwich Theorem
Reading materials:
Class notes
Topics covered in Lecture 18 (12 April'21)
Arrangement of Hyperplanes
Number of vertices of level k
Reading materials:
Sections 6.1 and 6.3 in [M02]
Topics covered in Lecture 19 (14 April'21)
Colorful Caratheodory theorem
Tverberg's Theorem
Reading materials:
Topics covered in Lecture 20 (27 April'21)
Set systems and Transversal
Packing and Matching Number
Reading materials:
Topics covered in Lecture 21 (29 April'21)
Introduction to VC Dimension
Reading materials:
Topics covered in Lecture 22 (31 April'21)
Sauer–Shelah Lemma (Shatter Theorem)
Reading materials:
Topics covered in Lectures 23 and 24 (4 May'21 and 6 May'21)
Topics covered in Lectures 25 and 26 (11 May'21 and 13 May'21)
Statement of Johnson–Lindenstrauss lemma
Gaussian Annulus Theorem
Proof of Johnson–Lindenstrauss lemma via Gaussian Annulus Theorem
Reading materials:
Topics covered in Lecture 27 (15 May'21)
Erdos-Ko-Rado Theorem
Upper bound on the number of vertices in a convex polytope
Reading materials: