## CS507: Computational Geometry

Instructor:

McGill University

### Exam 1 - Solutions - 2000

#### Question 1:

a) The conjecture is false!

This is a polygon which you've seen in class. Here x cannot completely see any edge.

b) Does this prove the induction impossible to prove? Not at all. The conjecture stated that every point outside P could completely see an edge, and this turned out to be false. However, if we're doing an induction proof, then we're not interested in every point, just the (n+1)st point, which we can select more carefully. For example, the following is true.

• For any simple polygon, every point outside the convex hull can completely see an edge.

Then a valid induction proof would remove an extreme point from the set, polygonize the remainder, and then add the point back in. Since the point is outside the convex hull, it can be added to the polygonization (forming an ear with the visible edge).

#### Question 2:

a) Suppose that the smallest enclosing circle C is determined by fewer than two points. If zero, then the radius circle can be shrunk until C touches a point of S, contradicting the fact that C is the smallest enclosing circle. If C touches one point p, then we can perturb C ever so slightly in the direction of p without changing its radius. Now C is not touching any points, and can therefore be reduced. Finally, C cannot be determined by more than three points of the set, as this would violate our general position assumption.

b) Suppose the smallest enclosing circle C is determined by three points of a non-acute triangle. Then there exists a diameter of the circle such that all three points are on one side of the diameter. Therefore we can move C slightly in the direction perpendicular to the diameter, such that all points of the set lie within the circle, and the three points of the triangle are no longer touching C. Now C is determined by zero points of the set, and therefore can be reduced as in part (a).

#### Question 3:

We must rotate S such that no two points of S are on a vertical line. So our goal is to first find a slope such that no line between any two points of S has slope , and then rotate S until is vertical. The easiest way to find such an is to find the steepest slope between any two points of the set. Then we can choose to be twice as steep.

Rotating a set takes linear time (just compute where each point ends up), all we must do is find the steepest slope of any two points in the set in O(n log n) time. To help me find the steepest slope, I use the following observation.

Lemma. Sort the list by increasing x-coordinate, breaking ties by taking the higher point first. Then the steepest slope is determined by a pair of points adjacent in the sorted list.

Proof by contradiction. Suppose the steepest slope is not determined by a pair of adjacent points, but rather by a pair of non-adjacent points. Let a and b the two points determining the steepest slope which are as close as possible in the sorted list. Because a and b are non-adjacent, there must be some point c between them. We then have three cases:

Case 1: c is below the line ab. Then the slope of the line cb is steeper than the slope of ab. The line cb is not vertical, since c is below the line ab and is before b in the sorted list. Contradiction.

Case 2: c is above the line ab. Then the slope of the line ac is steeper than the slope of ab. The line ac is not vertical, since c is above the line ab and is after a in the sorted list. Contradiction.

Case 3: c is on the line ab. Then the line ac has the same slope as ab. But a and c are closer in the sorted list than a and b are, which violates the fact that a and b are the two points determining the steepest slope which are as close as possible in the sorted list. Contradiction.
QED

By our lemma, the steepest slope is determined by a pair of points adjacent in our sorted list. We can compute this slope with the following algorithm:

1. Sort the points on two keys as follows:
• Sort in order of increasing x-coordinate.
• When there is a tie, sort by decreasing y-coordinate.
2. Take the maximum slope of all adjacent points (disregarding pairs on a vertical line).

We then rotate counterclockwise by a slope less than this maximum, say by half that amount. The algorithm involves one sorting and then selects the maximum from a list, so it clearly runs in time O(n log n).