CS 164 - Computational Geometry Homework 6, 50 Points
Due: Friday, March 9, 11:55pm
Assignments must be typed and turned in using
the EEE system.
-
10 points.
Problem 7.5 from de Berg et al.
-
10 points.
Problem 7.11 from de Berg et al.
-
10 points.
(CS 164 students only)
Problem 8.1 from de Berg et al.
-
10 points.
(CS 266 students only)
Problem 8.3 from de Berg et al.
-
10 points.
Problem 8.6 from de Berg et al.
-
10 points.
Problem 8.15 from de Berg et al., except you should come up with algorithms
that have the desired time bounds for 8.15b and 8.15c
in the worst case, not expected case.
You may use O(n2 log n) space.