Exam 1 - Solutions - 2005
NOTE: These are only sketches of solutions.
I expect to see more details during exams.
The easiest way to determine the orientation of the given polygon
is to comupte its signed area. If the sign of the area is negative,
then the orientation is clockwise; otherwise, the orientation
is counterclockwise. Computing the area will take linear time.
Another way to find the orientation is to first find an extreme
point pi with say minimum x-coordinate,
and by computing the signed area of triangle pi-1pipi+1
determine the orientation of the polygon. The running time is
bounded by that of finding an extreme point, which is linear.
Here, it is important to do this check for an extreme point
because we need to make sure that the area pi-1pipi+1
is in the interior of the polygon.
The algorithm for this question is basically the same as the
one seen in class, but we have to be careful when handling degeneracies.
The algorithm goes as follows:
First, sort the points by x-coordinate, breaking ties with decreasing
y-coordinate. Pick two points pmin
and pmax having xmin
and xmax respectively. We know that
since not all the points are collinear, xmin
and xmax have to be different. Starting
from pmin and ending at pmax,
and for all the points that are strictly above the line
pminpmax, connect every
pi to the next point in the sorted
list which is strictly above pminpmax.
Similarly, for all the points that are below or on
the line pminpmax, connect
every pi to the next point in the
sorted list which is below or on pminpmax.
If one of the upper or lower chains is empty, then connect pmin
to pmax. The resulting structure is
a polygon monotone in the x-direction.
Why? Suppose your polygon is not monotone. This means that a
line L perpendicular to the x-axis will intersect
the polygon at more than two points. Since our polygon is composed
of two chains, then this means L intersect at
least one of the chains, say the upper, in more than one point.
Thus, suppose L intersect an edge pipi+1
of the upper chain with xi < xi+1.
If L intersects this chain at another edge e,
this means that the e has the x-coordinate of
one endpoint greater than xi+1 and
the other less than xi+1. But this
cannot happen because we sorted the points by x-coordinate. Contradiction.
We can make similar arguments for the lower chain. There fore
L intersects the polygon atno more than two points.
This induction proof was done in class. I will give a sketch
Base case: A triangle can easily be 3-colored by assigning a
distinct color to each vertex.
Induction step: Assume we can color any polygon up to n-1
vertices. Now suppose we are given a polygon with n
vertices. We know that this polygon contains an ear by the two-ears
theorem. So, find an ear with tip pi
and cut it off. What remains is a polygon on n-1
vertices which we know how to 3-color by assumption. After 3-coloring,
put the ear back and color the ear tip pi with
a color different than that of pi-1