The course is a graduate-level introduction to basic techniques used in the design and analysis of efficient geometric algorithms, including: convexity, triangulation, sweeping, spatial partitioning, and point location. Arrangements and Voronoi/Delaunay diagrams will be discussed in detail, with emphasis on recent developments using random sampling methods. The course will also cover some intersection, visibility, and range searching problems. The focus will be on data structures of general usefulness in geometric computing and the conceptual primitives appropriate for manipulating them. The impact of numerical issues in geometric computation will also be addressed. Applications to motion planning, visibility preprocessing, model-based recognition, molecular modeling, and geographical information systems will be used throughout to motivate the material.

Time: Tu/Th 1:15 -- 2:30 pm

Location: TCseq 201