Pre-requisites : CS204
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.
1. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.
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.