# InfoCoBuild

## Computational Geometry

Computational Geometry. 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. (from nptel.ac.in)

 Introduction

 Introduction using Basic Visibility Problems Lecture 01 - Introduction Lecture 02 - Visibility Problems The Maximal Points Problem Lecture 03 - 2D Maxima The Plane Sweep Technique and Applications Lecture 04 - Line Sweep Method Lecture 05 - Segment Intersection Problem Lecture 06 - Line Sweep: Rectangle Union Convex Hull Different Paradigms and Quickhull Lecture 07 - Convex Hull Lecture 08 - Convex Hull (cont.) Lecture 09 - Quick Hull Lecture 10 - More Convex Hull Algorithms Dual Transformation and Applications Lecture 11 - Insertion of Half Planes and Duality Lecture 12 - Insertion of Half Planes and Duality (cont.) Lower Bounds on Algebraic Tree Model Lecture 13 - Lower Bounds Point Location and Triangulation Lecture 14 - Planar Point Location Lecture 15 - Point Location and Triangulation (cont.) Lecture 16 - Triangulation of Arbitrary Polygon Voronoi Diagram and Delaunay Triangulation Lecture 17 - Voronoi Diagram: Properties Lecture 18 - Voronoi Diagram Construction Lecture 19 - Delaunay Triangulation Randomized Incremental Construction and Random Sampling Lecture 20 - Quick Sort and Backward Analysis Lecture 21 - Generalized RIC (Randomized Incremental Construction) Lecture 22 - Randomized Incremental Construction (cont.) Arrangements and Levels Lecture 23 - Arrangements Lecture 24 - Applications of Zone Theorem and Arrangements Lecture 25 - Arrangements (cont.) Range Searching Lecture 26 - Range Searching: Introduction Lecture 27 - Orthogonal Range Searching Lecture 28 - Priority Search Trees Lecture 29 - Non-Orthogonal Range Searching Lecture 30 - Range Searching: Half Plane Range Counting Clustering Point Sets using Quadtrees and Applications Lecture 31 - Well Separated Partitioning Lecture 32 - Quadtrees Epsilon-WSPD (Well Separated Pair Decomposition) Lecture 33 - Construction of Epsilon-WSPD Lecture 34 - Construction of Epsilon-WSPD (cont.) Epsilon-Nets, VC Dimension and Applications Lecture 35 - Epsilon-Nets and VC Dimension Lecture 36 - Epsilon-Nets and VC Dimension (cont.) Lecture 37 - Geometric Set Cover Lecture 38 - Geometric Set Cover (with Bounded VC Dimension) Shape Analysis and Shape Comparison Lecture 39 - Shape Representation Lecture 40 - Shape Comparison

 References Computational Geometry 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, ...