\input ncs445hdr
% this is nfinalcs445.tex of March 7, 1983 10:24 PM
\def\rtitle{Final Examination}
\def\header{Final Examination}
\def\point#1{\hbox to size{\hskip .25in{#1}\hfil}}
\def\prob{\hangindent -2in after 0{\curfont S n}\ {\bf\count1}.\ \advcount1}
\setcount1 1
\sect{Final Examination, due 12:00 noon on Tuesday, March 15}
{\caveat Please hand in your exams to Phyllis Winkler or slip them under my door in MJ330.}\par
{\caveat This exam consists of 26 rather easy exercises, intended to test your understanding of the fundamental concepts covered in this course. For true/false type questions give a proof or a counterexample, as appropriate. You are only required to hand in any 15 of the 26 questions.}\par
\vskip 5pt
\prob Consider a polygonal tracing defined by $t$ tours of length $n1̌, n2̌, \ldotss, nť$ respectively. A complete specification of the tracing must include the locations of all vertices, as well as the adjacency relations between the vertices. What is the {\it minimal} additional information needed to complete the specification?\par
\prob Let $T↑\prime$ denote the tracing obtained from $T$ by switching its orientation ({\it solid} arrow-head). If $s$ denotes the sweep number, is it true that $s(x,T) = s(x,T↑\prime)$ for any $x$ not on $T$? What if $T$ is monostrofic? What if $T$ is convex?\par
\prob What is the degree of $P\cdot Q$ for the convex tracings $P$ and $Q$ shown?\par
\prob Show that if $X$ is convex then the equation $A\ast X=B$ has a solution in the tracing algebra. In other words, there is some tracing $X↑{-1}$ such that $A=B\ast X↑{-1}$. Prove that $X↑{-1}$ is also convex, and describe how to construct it from $X$. What condition, weaker than convexity, allows us to draw the same conclusion? Can you think of applications?\par
\prob Does either of the operations {\it product} or {\it dual product} distribute over the other?\par
\prob What class of piecewise smooth curves can you think of that strictly includes the polygonal tracings and is closed under convolution?\par
\prob Give a ‘‘convolutional’’ proof of the fact that two disjoint convex polygons have a separating line.\par
\prob Discuss why the degree of a line is the dual concept of the winding number of a point. What is the dual of the sweep number?\par
\prob Prove that $C = C↑{x-I}$ implies that tracing $C$ has a center of symmetry. Where is that center?\par
\prob We want to determine the convex hull of a star shaped polygon. Describe a pairing ({\it fibration}) of Alice and Bob, our favorite mountaineers, and a set of rules of the road so that as Alice goes around the polygon, Bob will be forced to describe its convex hull.\par
\prob Given $n$ lines in the plane, how fast can you compute the convex hull of all their intersection points?\par
\prob If we are given the Voronoi/Delaunay structure for $n$ points in the plane, can we then sort the points according to the $x$ coordinate in less than $O(n \lg n)$ time?\par
\prob Is a convex polygon that can be decomposed into the disjoint union of center-symmetric convex polygons itself center symmetric?\par
\prob Let $n$ points in the plane be given. Must a circle with diameter some {\it mst} edge for our set be point-free?\par
\prob Show that the smallest perimeter triangle of $n$ points in the plane is defined by three vertices that determine a non-empty region of the 3-Voronoi.\par
\prob We want to maintain a collection of {\it rooted} vertical line segments, that is, vertical line segments with their lower endpoint on the $x$-axis. For a given test point in the plane, a query consisits of reporting the first (if one exists) rooted segment to be intersected by an infinite horizontal ray emanating from the test point and proceeding to the right. Show that it is possible to implement collections of rooted segments so that insertion, deletion, and query each take time $O(\lg n)$. \par
\prob Draw the quad edge structure for the subdivision of the sphere shown.\par
\prob Show how, by using $O(n \lg n)$ storage, we can get a linear algorithm for deleting a point from a Voronoi/Delaunay diagram.\par
\prob Is the diameter of a point set an edge of the dual of the furthest point Voronoi?\par
\prob Can you construct a collection of $n$ points in the plane that has $n$ distinct diameters?\par
\prob How fast can you check if a point is contained in a convex polyhedron?\par
\prob How fast can you compute the volume of a convex polyhedron?\par
\prob How fast can you compute the {\it maximal} elements of a collection $n$ points in the plane? By maximal we mean those points in whose upper right quadrant no other point lies.\par
\prob Let $\Cscr$ be a collection of $n$ non-intersecting line segments in the plane. We say that segment $\alpha$ is to the left of segment $\beta$ if there is some horizontal line intersecting $\alpha$ to the left of $\beta$. Show that ‘‘left of’’ is a well defined and acyclic relation.\par
\prob In the situation described above, how fast can you compute a linear ordering of the segments consistent with the ‘‘left of’’ relation.\par
\prob Let $n$ points in the plane be given and consider any two triangulations $T1̌$ and $T2̌$ of these points. Can we always go from $T1̌$ to $T2̌$ by successive ‘‘swapping-rule’’ like transformations?\par
\vfill\eject\end