\input ncs445hdr
% this is nh7cs445.tex of February 21, 1983 9:35 PM

\def\rtitle{Homework 7}
\def\header{Homework 7}
\def\point#1{\hbox to size{\hskip .25in{#1}\hfil}}
\setcount1 34

\sect{Seventh Problem Set, due Thursday, March 3}

\prob Let $A$ be a site and let $X$ and $Y$ denote any two distinct Delaunay neighbors of $A$. Show that all other Delaunay neighbors of $A$ that lie inside the convex angle $\angle XAY$ are inside the circumcircle of triangle $AXY$, and all neighbors lying outside the angle are outside that same circle.\par

\prob Discuss how to adapt the divide-and-conquer Delaunay algorithm we presented in class so that, by ‘‘continuing on’’, it computes also the dual of the {\it furthest-point} Voronoi.\par

\prob We define the {\it $k$-Voronoi} subdivision of the plane determined by $n$ sites as the partition of the plane obtained by classifying points according to their $k$ nearest neighbors among the sites. Thus the standard Voronoi is the 1-Voronoi, and what we have been calling the furthest-point Voronoi is the $(n-1)$-Voronoi. Characterize the faces, edges, and vertices of the $k$-Voronoi subdivision. In addition give an $O(n \lg n)$ algorithm for constructing the 2-Voronoi subdivision of the $n$ sites.\par

\prob Given $n$ sites in the plane, show how Voronoi diagrams can be used to find the largest point-free circle with center inside the convex hull of the sites, and also the smallest circle containing all the sites (often called the {\it minimum spanning circle}).\par

{\caveat The last one is an extra credit problem.}\par

\prob Consider again $n$ sites in the plane. We are interested in the answers to circular queries asking for all the sites contained inside some arbitrary circle. How many distinct answers to such queries can there be? If your answer is not exact, then give both upper and lower bounds.\par

\vfill\eject\end