## CS507: Computational Geometry

Instructor:

McGill University

### Exam 1 - Solutions - 2003

#### Question 1:

A simple proof by contradiction is to assume that a point X is not covered and expand a circle around it until the boundary is touched. This cannot happen at a vertex. Then you immediately have a segment perpendicular to some edge that reaches X (the radius of the cirlce).

By contradiction: assume there is a point X not covered. Start with any strip si formed perpendicular to some edge ei =(Pi , Pi+1). Assume WLOG that X is "to the left" of the strip, i.e. the length |X-Pi| is greater than |X-Pi+1|. Then you continue with ei+1 and show that for X to not be covered, the same situation holds (due to convexity). This means that |X-Pi+1| is greater than |X-Pi+2|. Thus you continue around the polygon always yielding shorter and shorter lengths between X and successive polygon vertices. This eventually leads to a contradiction (when you return to Pi).

#### Question 2:

The most elegant answer is to consider any pocket of our non-convex polygon. This pocket is a polygon itself, it is either a triangle (= mouth), or it has at least 2 ears. Only one ear can "use" the pocket lid, thus the other ear is a mouth of the original polygon.

Another method is to consider any concave vertex V and claim that there must be some other vertex in the triangle Vi-1,V,Vi+1 (otherwise it is a mouth). At least one vertex in the triangle must be convex. In fact we cound find one such vertex K by using the Meister's sweep that was discussed in class. Then we can go on to claim that there must be another concave vertex along one of the chains from K to V. This process eventually comes to an end since at each iteration we have a smaller and smaller chain that contains a concave vertex. I expected a little bit of detail here, for full marks. This includes some reason for termination of the process "if i destroy one candidate mouth, then there must be another one somewhere".

#### Question 3:

The easiest method in my opinion is to sort by X and add vertices by increasing value. For each new vertex Xi, add two diagonals onto one of the edges of the last triangle formed (creating a new triangle). One of these diagonals will be to the previous vertex Xi-1, which is obviously visible from the current one. The other diagonal is NOT necessarily to Xi-2.
Creating monotone polygons with the typical methods seen in class (boat polygon, or drawing a line from Xmin to Xmax and creating two chains) does not necessarily yield a serpentine polygon. Let Xmin and Xmax be the only two vertices on a very long horizontal lower monotone chain (or lower hull). Now place Xmin+1 and Xmax-1 near the middle, just above the horizontal segment. Place all other points at much higher y-values. Now you wont get a serpentine polygon.