Princeton University
Computer Science Department

Computer Science 451
Computational Geometry

Bernard Chazelle

Fall 2017


Directory
General Information

Course Summary

Recommended book - Computational Geometry: Algorithms and Applications (3rd ed), by Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Springer, 2008.

Administrative Information

Lectures: MW 13:30-14:50, Room: PH145

Professor: Bernard Chazelle - 404 CS Building - 258-5380 chazelle[at sign]cs.princeton.edu

Undergraduate Coordinator: Colleen Kenny-McGinley - 210 CS Building - 258-1746 ckenny[at sign]@cs.princeton.edu

Teaching Assistants: Matheus Ferreira, mvxf[at sign]@cs.princeton.edu, and Udaya Ghai, ughai[at sign]@cs.princeton.edu.


HHW ASSIGNMENTS

Hwk1

Hwk2

Hwk3

Hwk4

Projects


LECTURE NOTES

Jeff Erickson's notes on convex hulls in the plane.

The Kirkpatrick-Seidel convex hull algorithm: the article.

Danny Sleator on Voronoi diagrams. More on Voronoi diagrams here.

For arrangements of lines, read this and David Mount's notes (pages 82 on).

David Kirpatrick's point location algorithm.

For notes on duality, read this. Jeff Erickson's notes on Tamal Dey's proof.