6.850 Geometric Computing
Introduction to the design and analysis of algorithms for geometric problems, in low- and high-dimensional spaces. Algorithms: convex hulls, polygon triangulation, Delaunay triangulation, motion planning, pattern matching. Geometric data structures: point location, Voronoi diagrams, Binary Space Partitions. Geometric problems in higher dimensions: linear programming, closest pair problems. High-dimensional nearest neighbor search and low-distortion embeddings between metric spaces. Geometric algorithms for massive data sets: external memory and streaming algorithms. Geometric optimization.
This class has 6.046 as a prerequisite.
6.850 will not be offered this semester. It will be available in the Spring semester, and will be instructed by P. Indyk.
This class counts for a total of 12 credits. This is a graduate-level class.
© Copyright 2015 Yasyf Mohamedali