CS 663: Computational Geometry

Course Contents:

Historical perspective: complexity notions in classical geometry. Towards computational geometry, geometric preliminaries, models of computation.

Geometric searching: point location problems, location of a point in a plannar subdivision, the slab method, the chain method, range - searching problems.

Convex hulls: problem statement and lower bounds. Graham's scan, Jarvis's march, quick hull technique, convex hulls in two and higher dimensions, extension and applications.

Proximity: divide and conquer approach, locus approach; the Voronoi diagram, lower bounds, variants and generalizations. Intersections, hidden-line and hidden surface problem.

The geometry of rectangles: application of the geometry of rectangles, measure and perimeter of a union of rectangles, intersection of rectangles and related problems.

Books and References:

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