Exam 1 - Solutions - 2003
(Solutions by Greg Aloupis)
NOTE: These are only sketches of solutions.
I expect to see more details during exams.
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).
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
Another method is to consider any concave vertex V
and claim that there must be some other vertex in the triangle
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".
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
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