\input cs445hdr
% this is hmwk4cs445.tex of February 1, 1982 2:24 PM

\def\title{Homework 4}
\def\header{Homework 4}
\setcount1 16

\sect{Fourth Problem Set, due Tuesday, February 9}

\prob Let $ABC$ be a triangle in the plane and let $M$ be a point randomly and uniformly chosen inside this triangle. Connect $M$ to the vertices $ABC$ by straight lines, and let $A↑\prime$, $B↑\prime$, and $C↑\prime$ be respectively where these lines intersect the sides opposite vertices $A$, $B$, and $C$ of the triangle. In this fashion the triangle $ABC$ is subdivided into six subtriangles with $M$ as a common vertex. Show that the expected area of each one of them is one sixth the area of $ABC$. Do so by an explicit computation, without using symmetry arguments.\par

{\caveat We saw in class that the convex hull of a simple polygon can be found in time $O(n)$, while the computation of the convex hull of a general collection of $n$ points requires time $\Omega(n\lg n)$. Another instance of this phenomenon is the result developed in the following sequence of problems. These problems lead to a linear algorithm for finding the nearest neighbor (vertex) of each vertex of a convex polygon. Again, it is known that for $n$ points in general position in the plane, $\Omega(n\lg n)$ time is required to solve the all nearest neighbors problem.}\par

\prob We say that a convex polygon has the {\it semi-circle property} if (i) its diameter is an edge, and (ii) all other vertices lie within a semi-circle erected on the diameter. Given a convex polygon $P$, show that, by drawing appropriate diagonals, $P$ can be decomposed into at four or fewer convex polygons with the semi-circle property. Show also that this decomposition can be done in linear time.\par

\prob Show that for any polygon with the semi-circle property, the nearest neighbor of each vertex is adjacent to it.\par

\prob Given a polygon $P$ with diameter equal to an edge, show that the nearest neighbor of each vertex can be found in linear time. Use this to show that the same is true for an arbitrary convex polygon.\par

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

\prob By an extension of the analysis done in class obtain an exact formula for the expected number of vertices on the convex hull of $n$ points chosen randomly, uniformly, and independently, within a convex quadrilateral in the plane. \par

\vfill\eject\end