Computational Geometry

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).

- 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:
- 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 true.

- 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):