Computational Geometry

Overview

Instructor: Prof. Pankaj Aggarwal, Department of Computer Science and Engineering, IIT Delhi.

This course covers lessons in Introduction using Basic Visibility Problems, The Maximal Points Problem, The Plane Sweep Technique and applications, Convex Hull Different Paradigms and Quickhull, Dual Transformation and Applications, Lower Bounds on Algebraic Tree Model, Point Location and Triangulation, Voronoi Diagram and Delaunay Triangulation, Randomized Incremental Construction and Random Sampling, Arrangements and Levels, Range Searching, Clustering Point Sets using Quadtrees and Applications, Epsilon-Nets VC Dimension and Applications, Shape Analysis and Shape Comparison.

Syllabus

Mod-01 Lec-01 Introduction.
Mod-01 Lec-02 Visibility Problems.
Mod-02 Lec-03 2D Maxima.
Mod-03 Lec-04 Line Sweep Method.
Mod-03 Lec-05 Segment Intersection Problem.
Mod-03 Lec-06 Line Sweep: Rectangle Union.
Mod-04 Lec-07 Convex Hull.
Mod-04 Lec-08 Convex Hull Contd.
Mod-04 Lec-09 Quick Hull.
Mod-04 Lec-10 More Convex Hull Algorithms.
Mod-05 Lec-11 Intersection of Half Planes and Duality.
Mod-05 Lec-12 Intersection of Half Planes and Duality Contd.
Mod-06 Lec-13 Lower Bounds.
Mod-07 Lec-14 Planar Point Location.
Mod-07 Lec-15 Point Location and Triangulation Contd....
Triangulation of Arbitrary Polygon..
Mod-08 Lec-17 Voronoi Diagram : Properties.
Mod - 08 Lec-18 Voronoi Diagram Construction.
Mod-08 Lec-19 Delaunay Triangulation..
Mod-09 Lec-20 Quick sort and Backward Analysis.
Mod-09 Lec-21 Generalized RIC.
Mod-09 Lec-22 RIC Continued.
Mod-10 Lec-23 Arrangements.
Mod-10 Lec-24 Zone Theorem and Application.
Mod-10 Lec-25 Levels.
Mod-11 Lec-26 Range Searching : Introduction.
Mod-11 Lec-27 Orthogonal Range searching.
Mod-11 Lec-28 Priority Search Trees.
Mod-11 Lec-29 Non - Orthogonal Range Searching.
Mod-11 Lec-30 Half - Plane Range Query.
Mod-12 Lec-31 Well Separated Partitioning.
Mod-12 Lec-32 Quadtrees Epsilon -WSPD.
Mod-12 Lec-33 Construction of Epsilon - WSPD.
Mod-12 Lec-34 Epsilon - WSPD to Geometric Spanner.
Mod-13 Lec-35 Epsilon-Nets & VC Dimension.
Mod-13 Lec-36 Epsilon-Nets & VC Dimension contd.
Mod-13 Lec-37 Geometric Set Cover.
Mod-13 Lec-38 Geometric Set Cover (with Bounded VC Dimension).
Mod-14 Lec-39 Shape Representation.
Mod-14 Lec-40 Shape Comparison.