Applications of Computational Geometry

Code: MA614 | L-T-P-C: 3-0-0-6

Prerequisites: MA 252 or equivalent

Basics of Computational Geometry - convex hull, line segment intersection, triangulation, linear programming, simplex range searching, voronoi diagram (nearest and farthest), arrangement and duality, visibility; Applications of geometric data structures and algorithms - geographic information system (GIS), robot motion planning, physical design in VLSI.

Texts:

1. M. de Berg, O. Chenong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Application, ,Springer-Verlag, 3rd Edn., 2008.
2. F. Preparata and M. Shamos, Computational Geometry: An Introduction, Springer-Verlag, 1985.

References:

1. K. Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1994.
2. H. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.
3. C. J. O'Rourke, Computational Geometry, Cambridge University Press, 1998.