\input ncs445hdr
% this is nh4cs445.tex of January 26, 1983 8:08 PM

\def\rtitle{Homework 4}
\def\header{Homework 4}
\setcount1 17

\sect{Fourth Problem Set, due Thursday, February 3}

\prob It has been our standard convention to orient convex tracings so that the car traverses them counterclockwise while moving forwards. We saw that the convolution of two such tracings is another tracing of the same kind. Let $P$ be a convex tracing following this convention, but let $Q$ be a tracing obtained from a convex polygon traversed counterclockwise, but {\it with the car backing up}. What can you say about $C =P\ast Q$? Draw an example and give a simple description of the result, such as the ‘‘merge the edges according to slope’’ rule that we gave for convolving convex tracings. Let $C$ be separated from some point $x$ by a line. Show that as the car moves around $C$, it faces towards $x$, and away from $x$, exactly once each. These two positions define the {\it tangents} from $x$ to $C$.\par

If $Q$ is a convex tracing, let $Q↑\prime$ denote the tracing obtained by reversing everywhere the way the car faces (but not the way it moves). Show that if $P$ and $Q$ are disjoint convex tracings, then the outer common tangents of $P$ and $Q$ are parallel to the tangents from the origin to $P\ast (Q↑{-I})↑\prime$.\par

\prob We are given a left shadow $L$ and a right shadow $R$, both of size $O(n)$. Assume that the infinite horizontal edges of $L$ and $R$ occur at different altitudes, and that there is a a point $x$ contained properly in both shadows. Prove that the boundaries of $L$ and $R$ intersect at exactly two points. If we have available $x$, and the standard representations for $L$ and $R$, show that it is possible to compute the two intersection points of the boundaries in time $O(\lg n)$.\par

\prob In class we discussed rules for advancing Alice or Bob along their respective convex tracings, so that eventually Alice and Bob would simultaneously pass through each pair of intersecting edges. We proved that if Alice and Bob meet at a pair of intersecting edges, then they will also meet the first time they each arrive at the next intersecting pair of edges. Suppose Alice’s tracing has $a$ edges and Bob’s $b$, that they start on arbitrary edges of their respective tracings, and that the edges of the two tracings have some intersection. Show that in no more than $2a+2b$ steps Alice and Bob will meet at an edge intersection. This completes the proof that the algorithm based on the advancing rules correctly finds all intersection points of the tracings.\par

\prob Consider a set $\Sscr$ of $n$ points in the plane. The {\it diameter} of the set $\Sscr$ is defined to be largest interpoint distance between two points of $\Sscr$. Show that if $a$ and $b$ are points of $\Sscr$ whose distance equals the diameter, then $a$ and $b$ are vertices of the convex hull of $\Sscr$. Prove further that the normals to the segment $ab$ at $a$ and $b$ define two antipodal tangents of the convex hull of $\Sscr$. Use this observation to explain how, once the tracing defining the convex hull of $\Sscr$ is given, then the diameter of $\Sscr$ can be computed in $O(n)$ additional time.\par

\vfill\eject\end