Massachusetts Institute of Technology

6.838 - Geometric Computation

Instructor:

Piotr Indyk
Stata Center, G642, (617) 452-3402
E-mail: indyk(a)theory.lcs.mit.edu
Office hours: by appointment.

Textbook:
Computational Geometry:
Algorithms and Applications,
2nd edition.
Mark de Berg, Marc van
Kreveld, Mark Overmars, and
Ottfried Schwarzkopf
ISBN: 3-540-61270-X;
Spring-Verlag
At Quantum Books, Kendall Square

Time and Place:
TR 1-2:30pm
In Room 24-115

Units:
(3-0-9)
H-credit for graduate students

Fall'03 web page

Current Handouts: Course Information; Calendar;

Problem Sets: PS1 (PS PDF), PS2 (PS PDF), PS3 (PS PDF) +solutions (PS PDF), PS4 (PS PDF).

Lectures:

Lecture 1: Convex Hulls in 2D, and an applet for Andrew's algorithm
Lecture 2: Segment Intersection, and an applet for segment intersection.
Lecture 3: Linear Programming in Low Dimensions (last year), and an applet demonstrating Seidel's algorithm for linear programming in 2D (by Roger Hanna).
Lecture 4: Polygon Triangulation
Lecture 4: Polygon Triangulation, and an applet for polygon triangulation.
Lecture 5: Range Searching.
Lecture 6: Point Location.
Lecture 7: Duality and a duality applet.
Lecture 8: Voronoi Diagrams and an applet demonstrating Fortune's algorithm for Voronoi diagrams.
Lecture 9: Delaunay Triangulations. Applet as above (click on Delaunay triangulation).
Lecture 10: Binary Space Partitions and an applet for BSP.
Lecture 11: Motion Planning (PPT) and an applet for the Piano Mover's problem.
Lecture 12: Closest Pair in Higher Dimensions.
Reference: M. Smid, Closest Point Problems in Computational Geometry".
Lecture 13: Approximate Near Neighbor in High Dimensions (ignore slides 1..3).
Reference: A. Gionis, P. Indyk and R. Motwani, Similarity Search in High DImensions Using Hashing" .
Lecture 14: Low-Distortion Embeddings (slides 0..21).
Reference: J. Matousek, "Embedding finite metric spaces into Euclidean spaces", p. 349.
Lecture 15: Low-Distortion Embeddings II.
Reference: P. Indyk, "Algorithmic Aspects of Geometric Embeddings" .
Lecture 16: Geometric Streaming Algorithms (using Low-Distortion Embeddings).
Reference: Pankaj K. Agarwal, Sariel Har-Peled and Kasturi R. Varadarajan, Geometric Approximations via Coresets - Survey .
Lecture 17: External Memory Algorithms for Geometric Problems.
References: Summer School on Massive Data Sets (see the talk by Jeff Vitter).
Lecture 19: Geometric Optimization.

Dorit Hochbaum, Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM, 1985.
Sanjeev Arora, Approximation schemes for NP-hard geometric problems: A survey.

Lecture 20: Geometric Pattern Matching.