Course Details
Subject {L-T-P / C} : CS6427 : Computational Geometry { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Dr. Tapas Kumar Mishra
Syllabus
Introduction: typical problems, applications and shortcomings. [1 hr]
Fixed-Radius Nearest Neighbors and Geometric Basics - introduction to affine geometry. [2 hr]
Convex hulls: introduction, Grahams scan algorithm, Divide and conquer algorithm,
Quick hull, Jarvis March, Chan's algorithm. [3 hr]
Line segment intersection: Parametric representation, Plane sweep algorithm. [3 hr]
Planar Graphs, Polygons and Art Galleries. [3 hr]
Polygon Triangulation. [3 hr]
Half-plane Intersection problem, point-line duality. [3 hr]
Linear Programming: LP in higher dimensional spaces, Deterministic incremental construction,
Randomized construction, Smallest enclosing disk problem. [3 hr]
Orthogonal Range Searching and Kd trees. Segment trees and red blue intersections. [3 hr]
Planar point location and trapezoidal maps. [3 hr]
Voronoi's diagram: Fortunes algorithm. [3 hr]
Delaunay Triangulations. [3 hr]
Line arrangements: Application of arrangements. [3 hr]
Shortest Paths and Visibility Graphs. [3 hr]
Course Objectives
- To learn the basic concepts of convex hulls.
- To learn point location, range queries, Voronoi diagram and Delunay triangulations.
- To learn half-plane intersection, application to linear programming.
- To learn the different Geometric searching and Sweep techniques.
Course Outcomes
After carrying out the course, students will: <br />1. understand the concepts of convex hulls and its applications in real world problems <br />2. comprehend the notions of linear programming through the application of half-plane intersections <br />3. master the concepts of point location in planar maps <br />4. have a better understanding of range queries, Voronoi diaghrams and Delunay triangulations.
Essential Reading
- Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld and Mark Overmars, Computational Geometry: Algorithms and Applications, Springer
- Joseph O' Rourke, Computational Geometry in C, Cambridge University Press
Supplementary Reading
- David Mount, Lecture notes, NA , http://www.cs.umd.edu/~mount/754/Lects/754lects.pdf
- F. P. Preparata and Michael I. Shamos, Computational Geometry: An Introduction, Springer
Journal and Conferences
- Surveys on Discrete and Computational Geometry: Twenty Years Later. Jacob E. Goodman, János Pach and Richard Pollack, Editors. Contemporary Mathematics. 2008. http://dx.doi.org/10.1090/conm/453