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 Fridays 2:30-3:30pm in Bren 4082). The teaching assistant is Alvin Chiu (office hours Tuesdays 4-5pm, ICS458F and Wednesdays 1-2pm, ICS458F). There is an online discussion forum on Ed Discussion.
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. For CS 266, I will also post a weekly graduate reading assignment from the computational geometry research literature; students are expected to understand at least the introductions to these papers, and I may include questions on these in 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, 11:00–12:20pm, in Rowland Hall 101. The final exam will be in the same place on Tuesday, December 8, 10:30AM–12:30PM. Lectures will also be in person only. Lecture slides for each topic will be posted on this page prior to each lecture, linked to the topic description. Except for students with special arrangements through the UCI Disability Services Center, all exams will be in person only.
Tentative Schedule
- Week 0 (September 24).
- Introductory lecture: Area and coordinates.
- No reading or practice problems this week.
- Week 1 (September 29, October 1).
- Geometric primitives and convex hulls [Chap. 1].
- Projective geometry; line segment intersection [Chap. 2; Sec. 8.2].
- Practice problem set 1.
- Graduate reading: Making Quickhull More Like Quicksort: A Simple Randomized Output-Sensitive Convex Hull Algorithm (Goodrich & Kitagawa, arXiv:2409.19784)
- Week 2 (October 6, 8).
- Arrangements of lines [Chap. 8].
- Polygon triangulation [Chap. 3].
- Practice problem set 2.
- Graduate reading: Irrational Guards are Sometimes Needed (Abrahamsen, Adamaszek, and Miltzow, arXiv:1701.05475). There's a stronger result by the same authors in _JACM_ 2021 but I think the 2017 paper is easier to read.
- Week 3 (October 13, 15).
- Visibility and shortest paths [Chap. 15].
- Quadtrees and mesh generation [Chap. 14].
- Graduate reading: Approximate Euclidean shortest paths amid convex obstacles (Agarwal, Sharathkumar, and Yu, SODA 2009).
- Week 4 (October 20, 22).
- First midterm exam, Tuesday, October 20
- Three-dimensional convex hulls [Chap. 11].
- No reading or practice problems this week because of the midterm.
- Week 5 (October 27, 29).
- Linear programming. LP-type problems [Chap. 4].
- Graduate reading: Optimal Point Placement for Mesh Smoothing (Amenta, Bern, & Eppstein, J. Algorithms 1999).
- Week 6 (November 3, 5).
- Point location and the locus method [Chap. 6].
- Voronoi diagrams [Chap. 7].
- Graduate reading: Non-Euclidean Erdős-Anning Theorems (Eppstein, Symp. Comp. Geom. 2025).
- Week 7 (November 10, 12).
- Delaunay triangulations and minimum spanning trees [Chap. 9].
- Second midterm exam, Thursday, November 12
- No reading or practice problems this week because of the midterm.
- Week 8 (November 17, 19).
- Range searching, kD-trees, and quadtrees [Chap. 5].
- Segment trees and interval trees [Chap. 10].
- Graduate reading: Finding relevant points for nearest-neighbor classification (Eppstein, Symp. Simplicity in Algorithms 2022).
- Week 9 (November 25, 27).
- Onion layers and fractional cascading [Chap. 5].
- Thanksgiving holiday, November 27
- Graduate reading: Grid peeling and the affine curve-shortening flow (Eppstein, Har-Peled, & Nivasch, ALENEX 2018 & Experimental Math. 2020).
- No practice set this week!
- Week 10 (December 2, 4).
- Binary space partitions and ray shooting [Chap. 12].
- Motion planning and configuration spaces [Chap. 13].
- Graduate reading: TBA.
- Final exam week.
- Final exam, December 8, 10:30AM–12:30PM