NPTEL : ACM Summer School on Geometric Algorithms and their Applications (Special Lecture Series)

Co-ordinators : Prof. Arijit Bishnu


Lecture 1 - Introduction to Computational Geometry

Lecture 2 - Convex hull

Lecture 3 - Quick hull

Lecture 4 - Plane sweep algorithm

Lecture 5 - Voronoi Diagram - I

Lecture 6 - Convex Geometry - I

Lecture 7 - Convex Geometry - II

Lecture 8 - Incidence Geometry - I

Lecture 9 - Incidence Geometry - II

Lecture 10 - Plane sweep algorithm

Lecture 11 - Polygon Triangulation

Lecture 12 - Geometric and Abstract Simplicial Complexes

Lecture 13 - Convex Polytopes and Polyhedra

Lecture 14 - Art Gallery Theorem

Lecture 15 - Smallest Enclosing Disc

Lecture 16 - Point Hyperplane Duality

Lecture 17 - Voronoi Diagrams and Delaunay triangulations - I

Lecture 18 - Voronoi Diagrams and Delaunay triangulations - II

Lecture 19 - Point Location

Lecture 20 - Range Searching (KD Tree)

Lecture 21 - Range Searching (Range Tree)

Lecture 22 - Visibility Graph and motion planning

Lecture 23 - Geometric Approximation: The Shifting Strategy, Hochbaum and Mass, 1984

Lecture 24 - Application of incidence geometry in combinatorics

Lecture 25 - Robot motion planning and visibility

Lecture 26 - Reeb Graph Introduction and Morse Theory basics

Lecture 27 - Reeb Graph Properties

Lecture 28 - Reeb Graph Algorithms, Applications

Lecture 29 - Arrangements - I

Lecture 30 - Linear Programming

Lecture 31 - Arrangements - II

Lecture 32 - Zone Theorem and Application

Lecture 33 - Randomized Incremental Construction - I

Lecture 34 - Randomized Incremental Construction - II

Lecture 35 - VC-dimension, Epsilon-nets, LP-based approximation for Geometric Covering

Lecture 36 - Quasi-uniform Sampling for Weighted Covering Problems.

Lecture 37 - Local Search for Packing and Covering

Lecture 38 - PTAS via Local Search - I