\input cs445hdr
% this is hmwk2cs445.tex of January 18, 1982 10:15 AM
\def\title{Homework 2}
\def\header{Homework 2}
\setcount1 6
\sect{Second Problem Set, due Tuesday, January 26}
\prob In class we defined the extremal points of a point set in the plane as those that lead to non-trivial intervals in the ``direction-of-sweep’’ circle. Show that the extremal points of our set are exactly those with the property that whenever they are in the (closed) triangle formed by some three points of our set, they coincide with one of the vertices of the triangle.\par
\prob Given $n$ points in the plane, show that there always exists a {\it simple} polygon with the given points as its vertices. Give an efficient algorithm to compute such a polygon, that is to order the points in the sequence in which they would occur as vertices of such a polygon. Be careful in your handling of degenerate cases. (It is known that the closed polygonal path connecting the points of minimum total length is simple, but computing that path is an NP-complete problem. That is the {\it traveling salesman} problem.)\par
Show that if we are given five points, then we can form twelve closed polygons using all the points as vertices, each exactly once. Of these twelve show that at least four are non-simple.
\prob In class we discussed Graham’s algorithm for finding the convex hull of a finite collection of points. This algorithm is based on sorting the points polarly around some point interior to the convex hull. Devise and describe a variant of this algorithm based on sorting the points along the $x$-coordinate instead. Which variant do you think is preferable in a practical sense?\par
\prob Given $n$ points in the plane, locate two circles such that each point is in some circle, and the maximum radius is a minimum. This is known as the {\it police station} problem, as it can be thought of as asking for the location of two police stations, so that the response time to any of a finite crime locations is minimized. What is the running time of your algorithm? Does your solution generalize to $k$ circles?\par
{\caveat The following is an extra credit problem. It deals with yet some more variants on the msc.}
\prob Given $n$ points in the plane, find the smallest circle that encloses at least $k$ of the points. Dually, given $n$ points in the plane, find the maximum number of them that can be enclosed in a circle of radius $R$. \par
\vfill\eject\end