Computational Geometry

The 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 .INTENDED AUDIENCE :4 th year undergraduate or beginning graduate studentsPREREQUISITES : Data Structures and AlgorithmsINDUSTRY SUPPORT : Nil

Week 1 : Introduction and Basic ProblemsWeek 2 : Plane Sweep TechniqueWeek 3 : Convex Hull and AlgorithmWeek 4 : Duality Transform and ApplicationWeek 5 : Lower Bound TechniquesWeek 6 : Point Location and TriangulationWeek 7 : Voronoi Diagram and Delaunay TriangulationWeek 8 : Arrangements and LevelsWeek 9 : Range SearchWeek 10 : Clustering Point sets using Quadtrees and ApplicationsWeek 11 : Epsilon-nets and VC DimensionWeek 12 : Shape Analysis