Pre-requisites : CS204

Syllabus :
Algorithmic design paradigms (divide and conquer, incremental, sweep line, and prune and search) and basic data structures (segment and interval trees). Geometricsearching: point locations (slab and chain methods) and range searching (kD and range trees) Convex hull: Graham's scan, gift wrapping, quick hull, divide-and-conquer Voronoi diagram and Delaunay triangulation: properties and construction algorithms (sweep line and divide-and-conquer algorithms). Visibility and Art gallery problems, motion planning and shortest paths. Arrangements and duality Line segments intersection problem closest pair computation.

Texts :
1. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.

References :
1. J. O'Rourke, Computational Geometry in C, 2nd Ed, Cambridge University Press, 1998.
2. M. Laszlo, Computational Geometry and Computer Graphics in C++, Prentice-Hall, 1996.
3. M. De Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer -Verlag, 1997.