Exam 1 - Solutions - 2000
(Solutions by Greg Aloupis)
NOTE: These are only sketches of solutions. I expect
to see more details during exams.
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:
- 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.
- 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).
|