Fall'01 web page

Current Handouts:  Course Information;    Calendar;    Signup sheet

Problem Sets:PS1, PS2, PS4

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, and an applet demonstrating Seidel's algorithm for linear programming in 2D (by Roger Hanna).
• Lecture 4: Polygon Triangulation, and an applet for polygon triangulation.
• Lecture 5: Range Searching.
• Lecture 6: Point Location and two applets, by Brad Lassey and Marsette Vona (requires Java 2 Runtime Enviroment).
• 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: Convex Hulls in 3D and an applet for 3D Convex Hull.
• Lecture 11: Motion Planning and an applet for the Piano Mover's problem.
• Lecture 12: Binary Space Partitions and an applet for BSP.
• Lecture 13: Folding.
• Lecture 14: Quadtrees.
• Lecture 15: Kinetic data structures.
• Lecture 16: LP in Higher Dimensions.
• Lecture 17: Closest Pair in Higher Dimensions.
• Lecture 18: Approximate Near Neighbor in High Dimensions (ignore slides 1..3)
• Lecture 19: Low-Distortion Embeddings (slides 0..21).
• Lecture 20: Low-Distortion Embeddings II
• Lecture 21: Geometric Streaming Algorithms (using Low-Distortion Embeddings)
• Lecture 22: External Memory Algorithms for Geometric Problems
• Lecture 23: Geometric Pattern Matching
• Lecture 24: Combinatorial Geometry
• Lecture 25: Geometric Optimization