Spring 2003, Computational Geometry
Martin's Thursday, Feb 14 office hours cancelled.
Book rant: My apologies about the text book. The book store, seems
not to be able to commit to any specific time when this book will be
available (they now say Feb 14, but admit that they don't really
know). There is now a copy of the textbook available at the reserve
desk in Olin Library. I will keep in mind that many of you don't have
a book when I make homeworks (and, if it gets that far, exams) and
will try to give pointers to related online material.
Course Policies/ Syllabus
Book:
Computational Geometry, M. de Berg, M van Kreveld, M. Overmars,
O Schwarzkopf, Second Edition, Springer-Verlag
Lecture Notes:
Lecture 1
Lecture 2
Lecture 3
Lecture 4
Lecture 5, supplementary link: Subash
Suri's version of Dave Mount's lecture on plane sweep and DCEL (pdf)
Lecture 6, supplementary link: art gallery theorem
Lecture 7
Lecture 8
Lecture 9
Lecture 10
Lecture 11 (old)
Lecture 11.5 (new)
Lecture 12
Lecture 13
Lecture 14
Lecture 15
Lecture 16
Additional descriptions of fortune's algorithm
Animation of Fortunes Algorithm
another visualization
Voronoi Art
Lecture 17
Lecture 18
Lecture 19-20
Lecture 21
Homework 1, solutions
Homework 2, solutions
Homework 3
, Homework 3 Solutions
Homework 4
, Homework 4 Solutions
Homework 5
Homework 5 Solutions
(Optional PROJECTS)
fake Midterm (pdf)
fake Midterm Solutions (pdf)
NOTE: 1d (3 points in circle of radius 1) is GENERAL POSITION.