\input cs445hdr
% this is hmwk1cs445.tex of January 11, 1982 2:47 PM

\def\title{Homework 1}
\def\header{Homework 1}
\setcount1 1

\sect{First Problem Set, due Tuesday, January 19}

\prob Prove Jung’s Theorem in 3-space: the radius of the minimum spanning sphere of a collection of points of diameter $d$ is bounded by $d\sqrt{6}/4$.\par

{\caveat The following two problems illustrate the power of convexity.}\par

\prob Prove that every simple polygon inscribed in a bounded convex curve is convex. (A convex curve is the boundary of a convex figure). Conversely, show that if every set of $n$ points of a bounded curve $K$ comprises the vertices of a convex polygon, then the curve is convex. The assumption stated in the last sentence is in fact too strong, as the same conclusion follows from a weaker statement. What is that statement?\par

\prob Let $n$ points $A1̌, A2̌, \ldotss, Aň$ be given in the plane. Prove that a point $O$ exists in the plane such that on each side of any line $\lscr$ through the point $O$ there are at least $n/3$ of the given points (including points lying on the line $\lscr$ itself).\par

{\caveat The following problem asks that you carefully consider how you might code up a rudimentary, but frquently encountered, geometric computation. Please express your algorithm is PASCAL, ALGOL, or some similar language.}\par

\prob Consider two line segments in the plane. It is often required to know if they intersect. Write a short procedure that will test this as efficiently as you can make it.\par

{\caveat The following is an extra credit problem, as its solution may use the concept of affine transforms.}

\prob Show that the minimum area spanning ellipse of three points in the plane exists and is unique. Prove that the center of the ellipse is the centroid of the triangle determined by the three points, and that its area is $4\pi/3\sqrt{3}$ times the area of the triangle.\par

\vfill\eject\end