Courses with significant overlap with this course:

Semester of last offering:

Date of approval: dd-mmm-yyyy

Prerequisites:  

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 planar subdivision, the slab method, the chain method, range searching problems. Convex hulls: problem statement and lower bounds. Grahams scan, Jarviss march, quick hull technique, convex hulls in more than one dimension, extension and applications. Proximity: divide and conquer approach, locus approach; the Voronoi diagram, lower bounds, variants and generalizations. Inter sections, 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. 

Topics