Exam 2 - Solutions - 2000
(Solutions by Greg Aloupis)
NOTE: These are only sketches of solutions. I expect
to see more details during exams.
Run the Jarvis gift-wrapping convex hull algorithm, except
before closing the hull after h iterations keep
sweeping to find the first point on the second layer and so on.
The algorithm runs in O(n2) worst-case time (since h =
See Question 1 of exam 1999.
a) If a point pi is on the hull, there
is an empty halfplane L defined by a line through the
point. Take the ray from the point pi,
orthogonal to L, into the halfplane. Any point on this ray
is closer to pi than to any other site,
thus the voronoi region V(i) is unbounded.
Now, if a cell V(i) is unbounded, then similarly we
can argue that there exists a ray passing through pi
and that there exists a line L .... there exists a
b) In a furthest point voronoi diagram V every 3 neighboring
points define a circle containing all the points. The furthest point
Delaunay triangulation D is obtained by connecting the
vertices that are neighbors in V. Thus, the vertices of a
triangle in D are 3 neighboring vertices in V, and
hence a circle passing through the vertices of any triangle in D
will contain all the points.
This corresponds to constructing a convex hull of points in the
dual. If you didn't cover duality, don't worry about it.