YoVDO

Computational Geometry

Offered By: NPTEL via YouTube

Tags

Geometry Courses Computational Geometry Courses Voronoi Diagrams Courses

Course Description

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.


Taught by

nptelhrd

Tags

Related Courses

Computational Geometry
Saint Petersburg State University via Coursera
Geometric Algorithms
EIT Digital via Coursera
计算几何 | Computational Geometry
Tsinghua University via edX
Computational Geometry
Indian Institute of Technology Delhi via Swayam
A Geometry Engine from First Principles - Building CAM Software for 3D Printing
media.ccc.de via YouTube