This homework must be turned in electronically using the EEE system. The solutions must be submitted as PDF files.

From the de Berg et al. Computational Geometry textbook:

1. 10 points. (CS 164 students only) Problem 1.1
2. 10 points. Describe an O(n log n) time method for determining if two sets, A and B, of n points in the plane can be separated by a line.
3. 10 points. Problem 1.4 (Note: in part b, "surface" should be "area".)
4. 10 points. Problem 1.6.a
5. 10 points. Problem 1.8 (CS 164 students need only answer 1.8.a)
6. 10 points. (CS 266 students only) Problem 1.10