** Spring
Quarter '10 - '11**
**Class News:**
The class midterm will be held in the same classroom on Wedensday, May 18. The exam will be closed book/notes. However, you are allowed a 1-page crib-sheet of your own notes to help you remember class material (both sides of the paper can be used).
A CGAL help session was held on Wednesday, April 6, 4-5 pm, in Clark S361. The video and slides are here.
We will be trying out Piazzza as the CS268 bulletin board. Please set up your account!
**Class Objective:**
The course is an advanced undergraduate or 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 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 9:30-10:45 am
**Location**: Clark S361
**Instructor**: Leonidas
Guibas,
- E-mail: guibas@cs.stanford.edu
- Office: Clark S293 (650 723-0304)
- Office hours: Monday, 1:30-2:30 pm
**CA**: Daniel Chen
- E-mail:danielc@cs.stanford.edu
- Office: Clark S297 (650 725-6521)
- Office hours: Tuesday, 9:00-11:00 am, and Thursday, 2:00-3:00 pm
**Homeworks**:
Homework 1 |
Out: Monday, 11 April |
Due: Monday, 25 April |
Homework 2 |
Out: Monday, 25 April |
Due: Monday, 9 May |
Homework 3 |
Out: Monday, 9 May |
Due: Friday, 27 May |
**Programming project proposal** (applied track) due: Moday, 16 May
**Midterm**: In class, Wedneday, 18 May
These pages are maintained by **Leonidas
Guibas** *guibas@cs.stanford.edu*.
Last update: 7 April-2011 |