\input cs445hdr
% this is fincs445.tex of March 8, 1982 4:29 PM

\def\title{Final Exam}
\def\header{Final Exam}
\setcount1 1

\sect{Final Examination, due in class, Tuesday, March 9}

{\caveat Work on this test alone. You may look at any books or notes that you wish. Each question is worth three points. However, not all questions are of equal difficulty. For each problem provide either a short proof, or a counterexample. Please be concise and to the point.}\par

{\caveat You need only work out any ten of the fifteen questions below.}\par

\prob True or false? If $P$ is a convex polygon completely contained within convex polygon $Q$, then the perimeter of $P$ is no greater than the perimeter of $Q$.\par

\prob True or false? Given a set of $n$ points in the plane, then any three of them that define a triangle of maximum area (among all triangles with vertices in our set) must be {\it vertices} of the convex hull of the $n$ points.\par

\prob True or false? Given a set of $n$ points in the plane and two other points $x$ and $y$, then a point in our set which maximizes the sum of distances to $x$ and $y$ is a vertex of the convex hull of our set.\par

\prob True or false? Given $n$ horizontal line segments in the plane, there exists a straight line (in arbitrary orientation) intersecting them all if and only if the same is true for each triplet of the $n$ segments.\par

\prob True or false? As a point $p$ walks along the perimeter of a convex polygon $P$, its distance to another fixed line $\lscr$ switches from increasing to decreasing at most a constant (independent of the number of vertices of $P$) number of times.\par

\prob True or false? As a point $p$ walks along the perimeter of a convex polygon $P$, its distance to another fixed point $x$ switches from increasing to decreasing at most a constant number of times.\par

\prob True or false? Two disjoint convex polygons always have a separating line (allowed to contain boundary points of the polygons) which is an extension of a side of one of them.\par

\prob True or false? Given $n$ points in the plane and a test point $x$, we can decide if $x$ is in the convex hull of the other points in linear time.\par

\prob True or false? Given $n$ points on a straight line (not necessarily in sorted order), we can find the maximum interpoint gap (which is free of other points) in linear time. (If you answer true you must give an algorithm, else a lower bound proof).\par

\prob Let $n$ points be given in the plane, such that each point has exactly one nearest neighbor (among the other points). Consider the directed graph with nodes the given points and directed edges from each point to its nearest neighbor. What kinds of directed cycles can this graph have?\par

\prob True or false? Consider a triangulated simple polygon as a graph, with vertices the triangles and an edge between every two triangles sharing a common diagonal in the polygon. Then this graph is acyclic.\par

\prob It is known that the diameter of a set of $n$ points in the plane never arises as the interpoint distance of more than $n$ pairs of points. Construct a configuration which attains this bound.\par

\prob How can you use priority search trees to decide if a point is inside a given simple rectagon? (Don’t worry about performance issues).\par

\prob How should you arrange $n$ points in the plane so that their 1-Voronoi diagram has as few vertices as possible?\par

\prob Consider a set of points on the $xy$ plane and another point $O$ in space, not lying on the $xy$ plane. Map each point of our set to a point in space by ``inverting through $O$’’. For the inversion we use a fixed radius $r$ and map point $A$ on the $xy$ plane to point $A↑\prime$ in space such that $\leftv OA\rightv\leftv OA↑\prime\rightv = r↑2$, and $A$ and $A↑\prime$ lie on the same ray from $O$. Show how the convex hull of the primed points in space tells us what the vertices of the 1-Voronoi and furthest point Voronoi are for the original set.\par

\vfill\eject\end