NPTEL : Computational Geometry (Computer Science and Engineering)

Co-ordinators : Prof. Sandeep Sen


Lecture 1 - Introduction

Lecture 2 - Visibility Problems

Lecture 3 - 2D Maxima

Lecture 4 - Line Sweep Method

Lecture 5 - Segment Intersection Problem

Lecture 6 - Line Sweep: Rectangle Union

Lecture 7 - Convex Hull

Lecture 8 - Convex Hull Contd

Lecture 9 - Quick Hull

Lecture 10 - More Convex Hull Algorithms

Lecture 11 - Intersection of Half Planes and Duality

Lecture 12 - Intersection of Half Planes and Duality Contd

Lecture 13 - Lower Bounds

Lecture 14 - Planar Point Location

Lecture 15 - Point Location and Triangulation Contd...

Lecture 16 - Triangulation of Arbitrary Polygon

Lecture 17 - Voronoi Diagram : Properties

Lecture 18 - Voronoi Diagram Construction

Lecture 19 - Delaunay Triangulation

Lecture 20 - Quick sort and Backward Analysis

Lecture 21 - Generalized RIC

Lecture 22 - RIC Continued

Lecture 23 - Arrangements

Lecture 24 - Zone Theorem and Application

Lecture 25 - Levels

Lecture 26 - Range Searching : Introduction

Lecture 27 - Orthogonal Range searching

Lecture 28 - Priority Search Trees

Lecture 29 - Non - Orthogonal Range Searching

Lecture 30 - Half - Plane Range Query

Lecture 31 - Well Separated Partitioning

Lecture 32 - Quadtrees Epsilon -WSPD

Lecture 33 - Construction of Epsilon - WSPD

Lecture 34 - Epsilon - WSPD to Geometric Spanner

Lecture 35 - Epsilon-Nets & VC Dimension

Lecture 36 - Epsilon-Nets & VC Dimension contd

Lecture 37 - Geometric Set Cover

Lecture 38 - Geometric Set Cover (with Bounded VC Dimension)

Lecture 39 - Shape Representation

Lecture 40 - Shape Comparison