Computational Geometry


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