CS663A - Computational Geometry

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.