15-456 Computational Geometry

9 units, Carnegie Mellon University

How do you sort points in space What does it even mean This course takes the ideas of a traditional algorithms course, sorting, searching, selecting, graphs, and optimization, and extends them to problems on geometric inputs. We will cover many classical geometric constructions and novel algorithmic methods. Some of the topics to be covered are convex hulls, Delaunay triangulations, graph drawing, point location, geometric medians, polytopes, configuration spaces, linear programming, and others. This course is a natural extension to 15451, for those who want to learn about algorithmic problems in higher dimensions.

Prerequisites: 15-451 (min C)

Courseweave needs JavaScript to show sections, workloads and planning tools.