Learn · NPTEL

Course10610201140 lectures

Computational Geometry

Prof. Amit Kumar · IIT Delhi

Start with lecture 1 At NPTEL

Lectures

Introduction using Basic Visibility Problems

  1. Introduction Video
  2. Visibility Problems Video

The Maximal Points Problem

  1. 2D Maxima Video

The Plane Sweep Technique and applications

  1. Line Sweep Method Video
  2. Segment Intersection Problem Video
  3. Line Sweep: Rectangle Union Video

Convex Hull Different Paradigms and Quickhull

  1. Convex Hull Video
  2. Convex Hull Contd Video
  3. Quick Hull Video
  4. More Convex Hull Algorithms Video

Dual Transformation and Applications

  1. Intersection of Half Planes and Duality Video
  2. Intersection of Half Planes and Duality Contd Video

Lower Bounds on Algebraic tree model

  1. Lower Bounds Video

Point Location and Triangulation

  1. Planar Point Location Video
  2. Point Location and Triangulation Contd... Video
  3. Triangulation of Arbitrary Polygon. Video

Voronoi Diagram and Delaunay Triangulation

  1. Voronoi Diagram : Properties Video
  2. Voronoi Diagram Construction Video
  3. Delaunay Triangulation. Video

Randomized Incremental Construction and Random Sampling

  1. Quick sort and Backward Analysis Video
  2. Generalized RIC Video
  3. RIC Continued Video

Arrangements and Levels

  1. Arrangements Video
  2. Zone Theorem and Application Video
  3. Levels Video

Range Searching

  1. Range Searching : Introduction Video
  2. Orthogonal Range searching Video
  3. Priority Search Trees Video
  4. Non - Orthogonal Range Searching Video
  5. Half - Plane Range Query Video

Clustering Point Sets using Quadtrees and Applications

  1. Well Separated Partitioning Video
  2. Quadtrees Epsilon -WSPD Video
  3. Construction of Epsilon - WSPD Video
  4. Epsilon - WSPD to Geometric Spanner Video

Epsilon-Nets VC Dimension and Applications

  1. Epsilon-Nets & VC Dimension Video
  2. Epsilon-Nets & VC Dimension contd Video
  3. Geometric Set Cover Video
  4. Geometric Set Cover (with Bounded VC Dimension) Video

Shape Analysis and Shape Comparison

  1. Shape Representation Video
  2. Shape Comparison Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Delhi
Department
Computer Science and Engineering
Teacher
Prof. Amit Kumar
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed