ICS 266, Spring 2006:
Computational Geometry
General Course Information
Coursework will consist of weekly homeworks and a comprehensive final
exam. The course text will be Computational
Geometry Algorithms and Applications, 2nd ed., by de Berg, van Kreveld,
Overmars, and Schwarzkopf (Springer-Verlag, 2000). The course meets
Tuesdays and Thursdays, 11:00 - 12:20 in ICF 101.
Homeworks will be assigned on Thursdays, due in class the following Tuesday.
Due to lack of teaching assistance for graduate classes, we will be
employing the following homework grading policy: you must be present in
class Tuesday for your homework to be scored. At the start of the
lecture, I will go over the answers to the homeworks together with a
scoring rubric, and each student will grade his or her own homework
according to the rubric. I will then collect and record the graded
homeworks.
Tentative Schedule
- Week 1: Introduction and geometric primitives [Chap. 1]
- Week 2: Projective and non-Euclidean geometry [Sec. 8.2]
Homework 1 due Thursday, April 20
- Week 3: Arrangements of lines and segments [Chaps. 2,8]
Homework 2 due Thursday, April 27: Textbook problems 2.10, 2.11, 8.4
- Week 4: Triangulation and visibility [Chaps. 3,15]
Homework 3 due Thursday, May 4: Textbook problems 3.3, 3.6, 15.1, 15.6
- Week 5: Linear programming [Chap. 4]
Homework 4 due Thursday, May 11: Textbook problems 4.9, 4.12, 4.14
- Week 6: Orthogonal range searching [Chaps. 5,10,14]
Homework 5 due Thursday, May 18: Textbook problems 5.5, 14.12, 14.13
- Week 7: Point location, binary space partitions [Chaps 6,12]
Homework 6 due Thursday, May 25: Textbook problems 6.2, 6.15, 12.3, 12.4
- Week 8: Voronoi diagrams and Delaunay Triangulations [Chaps. 7,9]
Homework 7 due Thursday, June 1: Textbook problems 7.5, 7.7, 7.11, 9.4
- Week 9: Convex hulls [Chap. 11]
- Week 10: Non-orthogonal range searching [Chap. 16]
Other Course-Related Information