CS 164/266, Spring 2019:
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 Mon/Wed 4-5pm in Bren Hall 4082). The TA is Martha Osegueda, mosegued@uci.edu (office hours Tue/Wed 3-4pm in Bren Hall 4061). There is an online forum at Piazza (search for CS164).

For both courses, coursework will consist of weekly homeworks (to be turned in through GradeScope), a midterm, and a comprehensive final exam. The course grade will be weighted as 10% from homeworks, 40% from the midterm, and 50% from the final. Group work on homeworks is permitted; each student should turn in his or her own copy of the homeworks. 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.

Each course meets WMF 2:00-2:50, in ELH 100.

The final exam will be Wednesday, June 12, 10:30-12:30. Homeworks will be assigned on Fridays, posted on this web page, and due online on the following Friday. Homeworks will be graded 50% for effort, 50% for correctness on one of the assigned problems (chosen arbitrarily from each problem set).

Tentative Schedule

Week 1.
Introduction and geometric primitives; 2d convex hulls [Chap. 1]
Projective geometry [Sec. 8.2]
Homework 1 (exercise numbers from the text, with some modifications as follows), due Friday, April 12:
Week 2.
Arrangements of lines and segments [Chaps. 2,8]
Homework 2, due Friday, April 19:
Week 3.
Triangulation and visibility [Chaps. 3,15]
Homework 3, due Friday, April 26:
Week 4.
Linear programming [Chap. 4].
No homework because of midterm
 
Week 5.
Midterm, Monday, April 29.
Orthogonal range searching [Chaps. 5,10].
Homework 4, due Friday, May 10:
Week 6.
Quadtrees and mesh generation [Chap. 14]
Point location, binary space partitions [Chaps 6,12]
Homework 5, due Friday, May 17:
Week 7.
Voronoi diagrams and Delaunay Triangulations [Chaps. 7,9]
Homework 6, due Friday, May 24:
Week 8.
Convex polyhedra and convex polytopes. Euler's formula and the upper bound theorem. Computing three-dimensional convex hulls. Point containment and ray shooting for 3d polyhedra. [Chap. 11].
Homework 7, due Friday, May 31:
Week 9.
Memorial day holiday, Monday, May 27.
Motion planning and configuration spaces [Chap. 13]
Homework 8, due Friday, June 7:
Week 10.
Non-orthogonal range searching [Chap. 16]
Fractional cascading [Sec. 5.6]
Review session Friday, June 7
 
Final exam, Wednesday, June 12, 10:30–12:30
 

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