| Course Code: CS502 Course Name: Computational Geometry Prerequisites: 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. |