Spring Quarter '05 - '06
Class News:
06/01/2006: There will be no clas on Wednesday, June 7. Instead there will be a special class on Thursday, June 8, from 11:00 am to 12:15 pm, in Clark S362 (next to the usual room).
05/17/2006: . The slides for Nikola's lecturs can now be found under the `Useful Links' tab.
04/26/2006: The slides for Steve Oudot's lectures can now be found under the `Useful Links' tab.
04/17/2006: Nikola will give a special CGAL lecture right after class on Monday, 4/24, same room.
Class Objective:
The course is a graduate-level 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 recent developments using random sampling methods. The course will also cover intersection, visibility, and range searching problems. 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. Applications to meshing, motion planning, visibility preprocessing, model-based recognition, molecular modeling, and geographical information systems will be used throughout to motivate the material.
Students in the course can choose between a theoretical and an applied track. The difference will be in some of the homeworks. The assignments in the theory track will emphasize the mathematical aspects and the analysis techniques; those in the applied track will focus on data structures and implementation issues.
A good undergraduate course in algorithms, such as CS161 here at Stanford, is useful preparation. Students in the applied track should have some implementation experience with C/C++.
Time: Mo/We 2:45--4:00 pm
Location: Clark S361
Instructor: Leonidas Guibas,
- E-mail: guibas@cs.stanford.edu
- Office: Clark S293 (650 723-0304)
- Office hours: Tuesdays, 1:00-2:30 pm
- E-mail: nikolam@cs.stanford.edu
- Office: Clark S257 (650 725-6532)
- Office hours: Thursday, 11:00 am-12:00 noon, and Friday, 12:00 noon-2:00 pm.
These pages are maintained by Leonidas Guibas guibas@cs.stanford.edu.
Last update: May 25, 2006