Fall Quarter 2016-17

Class News:

Please see Piazza for information on the upcoming midterm.

Class Objective:

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

Mondays: 9/26/2016, 10/10/2016, 10/17/2016
Wednesdays: 9/28/2016, 10/12/2016, 10/19/2016

Note that this includes the *first* class meeting.

Instructor: Leonidas Guibas,

E-mail: guibas@cs.stanford.edu

Phone: (650) 723-0304

Office: Clark S293

Office hours: Tuesdays, 1:30 - 2:30 pm, in his office

CA: Minhyuk Sung

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

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: guibas@cs.stanford.edu.

Last update: 5 November 2016