Discrete Geometry (PhD Students, 2023-24)
Discrete Geometry (PhD Students, 2023-24)
Instructor Arijit Ghosh
Teaching assistant Soumi Nandi and Sutanoya Chakraborty
Description To study some interesting topics from Discrete Geometry
Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences
Class timings TBA
Syllabus
Basics of Lattice Theory
Geometric Transversal Theory
VC dimension and its applications
High-Dimensional Geometry
Concentration of Measure and its applications
Borsuk–Ulam Theorem and its applications
Non-embeddability
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
[S93] Rolf Schneider, Convex Bodies: The Brunn-Minkowski Theory, Cambridge University Press, 1993
[SA00] Micha Sharir and Pankaj K Agarwal, Davenport-Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 2000
[S22] Adam Sheffer, Polynomial Methods and Incidence Theory, Cambridge University Press, 2022
[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
TBA