Fall Quarter 2016-17
Please see Piazza for information on the upcoming midterm.
The course is an advanced undergraduate / low-level graduate introduction to basic techniques used in the design and analysis of efficient geometric algorithms, including: convexity, triangulation, sweeping, spatial partitioning, and point location. Arrangements and Voronoi/Delaunay diagrams will be discussed in detail, with emphasis on random sampling methods. The course will also cover certain geometric optimization, intersection, visibility, and range searching problems -- and approximation algorithms for such. The focus will be on data structures of general usefulness in geometric computing and the conceptual primitives appropriate for manipulating them. The impact of numerical issues in geometric computation will be addressed. In addition, the rudiments of computational topology will be covered. Applications to meshing, robot motion planning, visibility preprocessing, model-based recognition, molecular modeling, and geographical information systems will be discussed throughout to motivate the material.
A good undergraduate course in algorithms, such as CS161 here at Stanford, is useful preparation. Students should have some implementation experience with Java (preferably -- to be used in the assignments) or C/C++.
Time: Mon/Wed 3:00 - 4:20 pm
Location: Clark S361
Because of a scheduling conflict with the main classroom, the class will meet instead in Gates 219 (open space) on
Note that this includes the *first* class meeting.
Instructor: Leonidas Guibas,
CA: Minhyuk Sung
Textbook (recommended, not required): Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications, third edition, Springer-Verlag, 2008. ISBN # 978-3-540-77973-5.
Homeworks: These will be a combination of theory and programming problems
Midterm: In class, Wednesday, 16 November
There will be no course final.
These pages are maintained by Leonidas Guibas: email@example.com.
Last update: 5 November 2016