ACM Summer School on Geometric Algorithms and their Applications (USB)

Media Storage Type : 32 GB USB Stick

NPTEL Subject Matter Expert : Prof. Arijit Bishnu

NPTEL Co-ordinating Institute : IIT Madras

NPTEL Lecture Count : 38

NPTEL Course Size : 10 GB

NPTEL PDF Text Transcription : Available and Included

NPTEL Subtitle Transcription : Available and Included (SRT)

Lecture Titles:

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