\input cs445hdr
% this is hmwk3cs445.tex of January 22, 1982 2:38 PM

\def\title{Homework 3}
\def\header{Homework 3}
\setcount1 11

\sect{Third Problem Set, due Tuesday, February 2}

\prob Early on in the course we introduced the concept of the {\it diameter} of a finite point set in the plane, i.e., the maximum distance between a pair of points. Show that the endpoints of a diameter are always vertices of the convex hull of our collection of points. Show further that, if the convex hull of our set is given (as an ordered collection of vertices), then the diameter can be found in time linear in the number of points on the hull.\par

\prob Given a convex polygon $P$ and a line $\lscr$ in the plane, show that it is possible to decide if $\lscr$ intersects $P$ in time $O(\lg n)$.\par

\prob ({\it ``Peeling’’ a set.}) Let $S$ be a finite set of $n$ points in the plane. Define the {\it depth} of a point $p$ of $S$ to be the number of convex hulls that have to be stripped from $S$ until $p$ is removed. For example, all points of $S$ that lie on its convex hull have depth 1. Find $O(n↑2)$ algorithms which (1) compute the depth of each point in $S$ and (2) produce the points of $S$ in order of increasing depth.\par

\prob In class we briefly described an algorithm for finding the {\it outer} tangents of two disjoint convex polygons possessing a $x$-separator (that is, a separating line parallel to the $y$ axis). Given two such polygons, describe instead an algorithm for finding their {\it inner} tangents. Present your algorithm as an explicit program and be sure to handle all cases correctly. If the polygons have $m$ and $n$ vertices respectively, then your algorithm should run in time $O(m+n)$.\par

{\caveat The following is an extra credit problem.}

\prob Assuming that in the previous problem the points of least and greatest $x$ value are given for each of the two polygons, show that the inner (and outer tangents) can be found in time $O(\lg↑2 (n+m))$. \par

\vfill\eject\end