\input ncs445hdr
% this is nh6cs445.tex of February 16, 1983 8:16 PM

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

\sect{Sixth Problem Set, due Thursday, February 24}

\prob Exhibit a monotone subdivision of size $O(n)$ that causes the Lee-Preparata point-location search to take $O(\lg↑2n)$ time.\par

\prob The ‘‘coarsening’’ step in our adaptation of Kirkpatrick’s algorithm for point location in a rectangular subdivision requires that we locate a subset of the defining segments such that (1) its size is a fixed fraction of the whole, (2) each segment in the subset has bounded degree, and (3) each pair of segments in the subset is independent. Discuss the details of how this coarsening step can be implemented in linear time in the size of the subdivision.\par

\prob Consider a collection on $n$ points in the plane such that no four of them are cocircular. We know that in this case the Voronoi dual is a triangulation, the {\it Delaunay} triangulation. Show that the Delaunay triangulation satisfies the following property: if $A$, $B$, $C$, $D$ are four points such that $ABCD$ is a convex quadrilateral, and $ABC$ and $ACD$ are Delaunay triangles, then the smallest angle among those of these two triangles is larger than the smallest angle of triangles $ABD$ and $BCD$.\par

\prob Again, let a collection of $n$ points in the plane be given, no four cocircular. We saw that a circle passing through two of the points and containing no other point in its interior is a witness to the Delaunayhood of the edge joining the two points. Some Delaunay edges satisfy an additional property, namely that they intersect their Voronoi duals. Give a similar local condition that is a witness to an edge possessing this additional property (sometimes called the {\it Gabriel} property).\par

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

\prob Recall that all triangulations of a set of $n$ points in the plane have the same number of triangles, namely $t = 2(n-1)-k$, where $k$ is the number of points on the convex hull. We can linearly order all triangulations as follows: Map each triangulation into a vector of $t$ angles, consisting of the smallest angle of each of the $t$ triangles, and sorted in nondecreasing order. Now any two such vectors can be compared lexicographically. Show that a triangulation is the ("a", in case of degeneracies) Delaunay triangulation if and only if it is the maximal triangulation in this ordering.\par

This implies a property that makes Delaunay attractive for several applications, such as the the finite element method. It is a triangulation that makes the smallest angle of any triangle as large as possible, and so in this sense it tends to avoid extremely skinny triangles.\par

\vfill\eject\end