CS 164/266, Spring 2019:
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, firstname.lastname@example.org (office hours Mon/Wed 4-5pm in Bren Hall 4082).
The TA is Martha Osegueda, email@example.com (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
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).
- Week 1.
- Introduction and geometric primitives; 2d convex hulls
- Projective geometry [Sec. 8.2]
- Homework 1 (exercise numbers from the text, with some modifications as follows), due Friday, April 12:
- CS 164: 1.1 (hint for parts b and c: the shortest path between two
points in the plane is a straight line), 1.3 (but your algorithm should
take linear time, not $O(n\log n)$; you may assume that it is possible
to use the points as keys in a hash table in constant time per
operation), 8.6, 8.8.
- CS 266: 1.1, 1.6, 8.2, 8.6.
- Week 2.
- Arrangements of lines and segments [Chaps. 2,8]
- Homework 2, due Friday, April 19:
- CS 164: 2.5, 2.6, 2.12 (hint: use a plane sweep with a binary search tree whose elements are the triangles that are not surrounded by any other triangle), 8.14 (hint: it's more obvious what to do if you convert the points to their dual lines)
- CS 266: 2.6, 2.12, 8.4, 8.14
- Week 3.
- Triangulation and visibility [Chaps. 3,15]
- Homework 3, due Friday, April 26:
- CS 164: 3.2, 3.3, 15.1, 15.7(a,b)
- CS 266: 3.3, 3.4, 15.4, 15.7(a,b)
- 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:
- CS 164: 5.2, 5.4, 10.6(b).
- CS 266: 5.1, 5.4, 10.6(b).
- Week 6.
- Quadtrees and mesh generation [Chap. 14]
- Point location, binary space partitions [Chaps 6,12]
- Homework 5, due Friday, May 17:
- CS 164: 6.1, 12.4, 12.11(a), 14.10(a).
- CS 266: 6.2, 12.4, 12.11(a), 14.10(a).
- Week 7.
- Voronoi diagrams and Delaunay Triangulations [Chaps. 7,9]
- Homework 6, due Friday, May 24:
- CS 164: 7.5, 7.7, 9.2, 9.8
- CS 266: 71., 7.7, 9.2, 9.8
- 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:
- Both classes: 8.3, 11.2, 11.4, 11.7
- Week 9.
- Memorial day holiday, Monday, May 27.
- Motion planning and configuration spaces [Chap. 13]
- Homework 8, due Friday, June 7:
- Both classes: 13.1, 13.2, 13.3, 13.4. Hint for 13.4: The shape
is the same but the position is different. Explain how this is
- 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):