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 B28Textbook Cover


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

Homework 1 Out: Monday, 10 October Due: Monday, 24 October
Homework 2 Out: Monday, 24 October Due: Monday, 7 November
Homework 3 Out: Monday, 7 November Due: Monday, 5 December

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