Computational Geometry (M.Tech CS, 2026-27)

Instructors Arijit Ghosh

Status To begin from July 2026

Description Introduction to Computational Geometry

Prerequisites Mathematical maturity of a finishing undergraduate student in mathematical sciences

Class timings TBA

Syllabus

• Basics of convexity

• Basics of probability theory

• Lattices and Minkowski’s Theorem

• Planar graphs and triangulations

• Polygons and the art gallery problem

• Crossing lemma and its application

• Planar separator theorem and its applications 

• Incidence geometry

• Sweep-line algorithms

• Line arrangements

• Envelopes and counting k-sets

• Linear programming and its applications

• Geometric data structures 

• Point-line duality

• Voronoi diagrams and Delaunay triangulations

• Applications of randomization and probabilistic methods in geometry 

• VC dimension, Epsilon-nets (and samples), and their applications (like geometric cuttings)

• Dimension reduction in high-dimensional geometry and its applications

• Introduction to geometric approximation algorithms