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++.
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.
- E-mail: guibas@cs.stanford.edu
- Phone: (650) 723-0304
- Office: Clark S293
- Office hours: Tuesdays, 1:30 - 2:30 pm, in his office
- E-mail: mhsung@cs.stanford.edu
- Phone: (650) 391-6349
- Office: Clark S257
- Office hours: Wednesdays, 2:00 - 3:00 pm, and Fridays, 10:00 am - 12:00 noon, in Gates B28
There will be no course final. These pages are maintained by Last update: 5 November 2016 |
||||||||||