## CS507: Computational Geometry

Instructor:

McGill University

### Exam 1 - Solutions - 2005

#### Question 1:

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.

#### Question 2:

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.

#### Question 3:

This induction proof was done in class. I will give a sketch here.

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 and pi+1.