Course Co-ordinated by IIT Delhi
 Coordinators IIT Delhi

Untitled Document

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 .

.

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

Under development