## CS507: Computational Geometry

Instructor:

McGill University

### Exam 2 - Solutions - 2003

#### Question 1:

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 neighbors.
If they are not Gabriel neighbors, then the midpoint belongs to some other point's voronoi cell. So they can't be strong Voronoi neighbors.

#### Question 2:

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.

#### Question 3:

See the class notes. Even if you did not see the proof in class, you should be able to do this.

#### Question 4:

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.