Exam 2 - Solutions - 2003
(Solutions by Greg Aloupis)
NOTE: These are only sketches of solutions. I expect to
see more details during exams.
The midpoint of i and j is the center of their Gabriel circle.
If they are Gabriel neighbors, then the midpoint belongs to both
respective voronoi regions. All remaining points on the
segment(i,j) belong to the two points. So they are strong Voronoi
If they are not Gabriel neighbors, then the midpoint belongs to
some other point's voronoi cell. So they can't be strong Voronoi
We didn't cover *expected* time algorithms for convex hulls.
But the incremental algorithm (without presorting) you saw in
class is essentially random. See class notes for details.
See the class notes. Even if you did not see the proof in
class, you should be able to do this.
If you prove the hint, then you can sort the n lines by slope
and compute the intersections of adjacent lines in the ordering.
Then just take the hull of these intersection points.
So, about the hint: draw two lines. WLOG they can look like the x
and y axes (combinatorially there is no difference). Can the
intersection point be on the hull if the two lines do not have
adjacent slopes? Well, to get them to NOT have adjacent slopes, we
must draw at least 2 more lines. Basically we have to have a line
with a slope in each quadrant, if we were to translate all new lines
to the origin. ( So one new line can take care of the adjacency in
the top-left and bottom right quadrants, and another line can take
care of the top-right and bottom-left quadrants).
In any case, some line has a slope into the top-right quadrant. WLOG
let it intersect the positive x-axis (as opposed to the positive
y-axis). So then it also intersects the negative y-axis. Next , we
know there must exist a line with slope into the top-left quadrant.
If it intersects the negative x-axis (and negative y-axis), then the
origin is not on the hull. The same applies if the last line
considered intersects positive y-axis and positive x-axis.