|
|
MIT Electrical Engineering and Computer Science
Fall 2001 Catalogue Supplement |
TR 1-2:30, Room 4-237
Prof. Piotr Indyk, Room NE43-373, 2-3402, Prof. Seth Teller, NE43-252, 8-7885
Prereq.: Permission of instructor
3-0-9
This is a graduate course in principles and practice of geometric computation, intended to impart a solid grounding in fundamental techniques of computational geometry, and a feeling for what methods can be brought to bear on problems arising in other domains of computer science.
Topics include 2D Convex Hulls, Segment Intersection and Map Overlay, Low-Dimensional Linear Programming, and Polygon Triangulation.
Also Orthogonal Range Searching, Point Location and Spatial Indexing, Voronoi Diagrams, Robustness and Perturbation Schemes, Arrangements and Duality, Delaunay Triangulations.
Also Representing Polyhedra, Convex Hulls, Smooth Surfaces, Binary Space Partitions, Kinetic Algorithms, Robot Motion Planning, Quad- trees and Non-Uniform Meshing.
Also Visibility Data Structures, Medial Axis and Surface Reconstruction, Higher- and High-Dimensional Linear Programming, Closest Pair, Approx- imate Nearest Neighbor, Iterative Algorithms, Low-Distortion Embeddings, and Reductions to Approximate Nearest Neighbor.
Readings will come from the textbook, de Berg et al.'s Computational Geometry: Algorithms and Applications, and from selected classic and modern papers from the research literature. Each topic will be co-presented by students and instructors, with significant effort devoted ahead of time to the student's command of the material.
There will be four homework assignments, roughly one every three weeks. Each assignment will have a required theoretical component, and an optional theoretical or programming component. There will be no final or final projects.
Enrollment is by permission of the instructors, and may be limited. Please complete a signup sheet at the first class meeting.
http://graphics.lcs.mit.edu/classes/6.838/F01/