|
A study of geometry from an algorithmic perspective, this course examines classic problems such as The Art Gallery Problem, The Post Office Problem, and The Piano Movers' Problem. Computational Geometry focuses on the design and analysis of efficient algorithms to solve problems which can be stated in terms of basic geometric objects like points, lines, segments, polygons, etc. We will consider various strategies for building convex hulls, Voronoi diagrams, and Delaunay triangulations; finding nearest neighbors and closest pairs; as well as line segment intersection, linear programming, polygon triangulation, point location, and range searching. Prerequisite: MAT290 or CSC117&MAT230 or permission of instructor. | |||||||