# 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:
• 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]