CS 164/266, Fall 2023:
Computational Geometry

General Course Information

The two courses CS 164 (for undergraduates) and CS 266 (for graduate students) are co-located: they will have the same lectures, but different homework and exam problems. They will be taught by David Eppstein, eppstein@uci.edu (office hours Thursdays 1:30 – 2:30 in Bren 4082). The teaching assistant is Alvin Chiu, a.chiu@uci.edu (office hours Wednesdays 3:30 – 4:30 in ICS 458A). There is an online discussion forum on Canvas.

For both courses, I will assign weekly practice problem sets at the start of each week, covering that week's material, and I strongly recommend that all students do these, but they will not be collected and graded. Instead, solutions will be posted at the end of the week to "Resources" in Ed Discussion, and you can expect to see similar problems (or even in some cases the same problems) on the exams. There will be three exams (two midterms and a final) each covering the material from roughly one third of the class (not comprehensive), each equally weighted in the overall course grade. Exams will be closed book, closed notes, and closed friends.

The course text is Computational Geometry Algorithms and Applications, 3nd ed., by de Berg, van Kreveld, Overmars, and Cheong (Springer-Verlag, 2008). An electronic version is available for no charge from UCI internet addresses at SpringerLink.

The combined lecture for both courses will meet physically on Tuesdays and Thursdays, 9:30–10:50pm, in Steinhaus Hall, SH 134. The final exam will be in the same place on Thursday, December 14, 8:00–10:00am. Lectures will also be in person only. Links to the lecture notes for each topic will be posted on this page prior to each lecture. Except for students with special arrangements through the UCI Disability Services Center, all exams will be in person only.

Tentative Schedule

Week 0 (September 28).
Introduction; 2d convex hulls [Chap. 1]
Week 1 (October 3, 5).
Practice problem set 1
Coordinate systems and geometric primitives; projective geometry [Sec. 8.2]
Line segment intersection [Chap. 2]
Week 2 (October 10, 12).
Practice problem set 2
Arrangements of lines [Chap. 8]
Polygon triangulation [Chap. 3]
Week 3 (October 17, 19).
Practice problem set 3
Visibility and shortest paths [Chap. 15]
Quadtrees and mesh generation [Chap. 14]
Week 4 (October 24, 26).
First midterm exam, Tuesday, October 24
Three-dimensional convex hulls [Chap. 11].
Week 5 (October 31, November 2).
Practice problem set 4
Linear programming and LP-type problems [Chap. 4].
Week 6 (November 7, 9).
Practice problem set 5
Point location and the locus method [Chap. 6]
Voronoi diagrams [Chap. 7]
Week 7 (November 14, 16).
Practice problem set 6
Delaunay triangulations and minimum spanning trees [Chap. 9]
Binary space partitions and ray shooting [Chap. 12]
Week 8 (November 21, 23).
Second midterm exam, Tuesday, November 21
Thanksgiving holiday, November 23
Week 9 (December 28, 30).
Practice problem set 7
Range counting, kD-trees, and quadtrees [Chap. 5]
Range reporting, onion layers, and fractional cascading [Chap. 5]
Week 10 (December 5, 7).
Practice problem set 8
Segment trees and interval trees [Chap. 10]
Motion planning and configuration spaces [Chap. 13]
Final exam week.
Final exam, December 14, 8:00–10:00am

Sample exams from past years (not guaranteed to cover the same material as this year):