Basics of Discrete Geometry (B.Stat, 2023-24)

Instructor  Arijit Ghosh 

Status Completed

Description To study the basics of Discrete Geometry. This is a module for the course Special Topics on Algorithms (B.Stat, 3rd Year) taught by Krishnendu Mukhopadhyaya.

Syllabus

• Abstract and Geometric Simplicial Complexes

• Examples of Simplicial Complexes, for examples, Čech complex, Rips complex etc.

• Nerve and Nerve Theorem

• Polytopes and Polyhedra

• Upper Bound Theorem

• Voronoi Diagram and Delaunay Complexes

• Lifting, lower hull, upper envelope, and minimization diagrams

References

• [B+08] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer Verlag, 2008.

• [B19] Jean-Daniel Boissonnat, Frédéric Chazal and Mariette Yvinec, Geometric and Topological Inference, Cambridge University Press, 2018.

• [GH12] Bernd Gärtner and Michael Hoffmann, Computational Geometry, Lecture Notes, ETH, 2012.

• [K06] Vladlen Koltun, Advanced Geometric Algorithms, Lecture Notes, Stanford University, 2006.

• [M02] Jiří Matoušek, Lectures on Discrete Geometry, Springer, 2002.

• [M16] David M. Mount, Lecture Notes on Computational Geometry, Department of Computer Science, University of Maryland, 2016.

• [Z95] Günter M. Ziegler, Lectures on Polytopes, Springer-Verlag, 1995.

Lecture details

Topics covered in Lecture 1

• Affine independence, affine hull, and affine dimension

• Introduction to geometric and abstract simplicial complexes

• Examples of simplicial complexes

• Geometric realization of abstract simplicial complexes

• Čech complex and Nerve theorem (only statement)

• Niyogi, Smale, and Weinberger's Nerve Theorem (only statement)

• Reading materials:

  • • Chapter 2 from [B19]

    • Chapter 1 from [K06]

• Additional reading materials:

  • • Niyogi, Smale, and Weinberger's papers [NSW08, NSW11]

Topics covered in Lecture 2

• Introduction to convex polytopes and polyhedra

• Facial structure of polytope and polyhedron 

• Simplicial polytopes and simple convex polyhedra 

• Point-hyperplane duality 

• Reading materials:

  • • Chapter 3 from [B19]

• Additional reading materials:

  • • Chapters 0 and 1 from [Z95]

Topics covered in Lecture 3

• Lower hull and Upper envelope of a point set

• Cellular complexes and dual complexes

• Duality between the lower hull and upper envelope of a point set

• Upper Bound Theorem

• Reading materials:

  • • Chapter 3 from [B19]

Topics covered in Lecture 4

• Lower envelopes and minimization diagrams 

• Voronoi diagrams 

• Delaunay complex as the nerve of Voronoi diagram 

• General position with respect to spheres 

• Delaunay Triangulation Theorem 

• Duality between Delaunay Triangulations and Voronoi driagrams

• Reading materials:

  • • Chapters 3 and 4 from [B19]