ICS 164, Spring 2008:
Computational Geometry
General Course Information
Coursework will consist of weekly homeworks, a midterm, 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
Mondays, Wednesdays, and Fridays, 9:00 - 9:50 in Bren 1300.
Homeworks will be assigned on Fridays, due in the ICS distribution center the following Friday.
Tentative Schedule
- Week 1: Introduction and geometric primitives [Chap. 1]: polygon
area; 2d convex hulls; numerical issues.
Homework 1 due Friday, April 11.
- Week 2: Projective geometry [Sec. 8.2]; geometric
transformations.
Homework 2 due Friday, April 18.
- Week 3: Arrangements of lines and segments [Chaps. 2,8].
Homework 3 due Friday, April 25.
- Week 4: Triangulation and visibility [Chaps. 3,15]
- Week 5: Linear programming [Chap. 4]. MIDTERM, Friday, May 2.
- Week 6: Orthogonal range searching [Chaps. 5,10,14]
Homework 4 due Friday, May 16.
- Week 7: Point location, binary space partitions [Chaps 6,12].
Homework 5 due Friday, May 23.
- Week 8: Voronoi diagrams and Delaunay Triangulations
[Chaps. 7,9].
Homework 6 due Friday, May 30.
- Week 9: NO CLASS MONDAY MAY 26 (Memorial Day holiday); 3d Convex hulls [Chap. 11]
- Week 10: Non-orthogonal range searching [Chap. 16]
Homework 7, due Monday, June 9: BKOS exercises 5.10(a,b), 11.2, 16.1
Other Course-Related Information