Computational Geometry

The two courses CS 164 (for undergraduates) and CS 266 (for graduate students) are co-located this year: they will have the same lectures, but different homework and exam problems.

For both courses, coursework will consist of weekly homeworks, 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 Tuesdays and Thursdays, 3:30-4:50, in ~~PSCB
140~~ MOVED
TO STEINHAUS
134 as of April 6.

The final exam will be Tuesday, June 10, 4:00-6:00. Homeworks will be assigned on Thursdays, posted on this web page, and due at the start of the lecture on the following Thursday. The teaching assistant is Michael Bannister, mbannist@uci.edu; his office hourse are Monday 2:30-4:30 in Bren 4219 and Wednesday 1:00-3:00 in Bren 3013.

- Week 1: Introduction and geometric primitives; 2d convex hulls
[Chap. 1]; Projective geometry [Sec. 8.2].

Homework, due April 10:- For CS 164: 1.1, 1.9, 8.2, 8.6
- For CS 266: 1.6, 1.10, 8.2, 8.6

- Week 2: Arrangements of lines and segments [Chaps. 2,8].

Homework, due April 17:- For CS 164: 2.5, 2.11, 8.3, 8.14
- For CS 266: 2.3, 2.11, 8.4, 8.14

- Week 3: Triangulation and visibility [Chaps. 3,15].

Homework, due April 24:- For CS 164: 3.2, 3.3, 15.1, 15.2
- For CS 266: 3.11, 3.14, 15.2, 15.4. For full credit in problem 3.14, your algorithm should take linear time.

- Week 4: Linear programming [Chap. 4].
- Week 5: MIDTERM, Tuesday, April 29.
- Weeks 5-6: Orthogonal range searching [Chaps. 5,10,14].

Homework, due May 8:- For CS 164: 4.11, 4.14, 5.6, 5.9
- For CS 266: 4.11, 4.14, 5.1, 5.10

- For CS 164: 10.1, 10.12(a), 14.1, 14.6
- For CS 266: 10.1, 10.6(c), 14.6, 14.12

- Week 7: Point location, binary space partitions [Chaps 6,12].

Homework, due May 22:- For CS 164: 6.1, 6.5, 12.3, 12.4
- For CS 266: 6.13, 6.15, 12.4, 12.10

- Week 8: Voronoi diagrams and Delaunay Triangulations [Chaps. 7,9].

Homework, due May 28:- For CS 164: 7.5, 7.7, 9.2, 9.17
- For CS 266: 7.7, 7.11, 9.11, 9.17

- Week 9: 3d Convex hulls [Chap. 11].

Homework, due June 4:- For CS 164: 11.2, 11.7, 11.8
- For CS 266: 11.2, 11.4, 11.8

- Week 10: Non-orthogonal range searching [Chap. 16]; Fractional cascading [Sec. 5.6]

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