\input ncs445hdr
% this is nh5cs445.tex of February 8, 1983 11:35 PM
\def\rtitle{Homework 5}
\def\header{Homework 5}
\def\point#1{\hbox to size{\hskip .25in{#1}\hfil}}
\def\dom{\mathop{\hbox{\bf dom}}}
\setcount1 21
\sect{Fifth Problem Set, due Thursday, February 17}
{\caveat This set has six problems, but they are all pretty easy.}\par
\prob Prove that for a simple subdivision of a manifold, as defined in class the following hold:\par
\vskip 6 pt plus 1 pt
\point{(a) each edge in incident to two vertices}
\point{(b) each edge is incident to two faces, and}
\point{(c) each each face is bounded by a single ring of edges and vertices.}
\prob Prove that every edge algebra can be realized by some double subdivision.\par
\prob Give a straight-line program of twelve {\fx MakeEdge} calls followed by a number of {\fx Splice} calls whose effect is to create the spherical subdivision corresponding to a cube. What is the result on the cube of now running the {\fx Splice} calls in the reverse order?\par
\prob Under what conditions do {\fx Splice[a,b]} and {\fx Splice[c,d]} commute?\par
\prob Let $\Rscr$ be a collection of rectangles in the plane, oriented with their sides parallel to the axes. We write $R1̌ \dom R2̌$ for two rectangles $R1̌$ and $R2̌$ in our collection to indicate that the upper right hand corner of $R2̌$ is above and to the right of the lower left hand corner of $R1̌$, as in the example below.\par
\vskip 1.5in
Show that the relation $\dom$ is acyclic.\par
\prob The {\it longest common ancestor} of two bit strings $\alpha$ and $\beta$ of length $n$ is defined to be another bitstring of length $n$ that starts out on the left with the longest common prefix of $\alpha$ and $\beta$ and is padded on the right with ‘‘$100\ldotss0$’’. Discuss how the least common ancestor function can be computed in constant time, using standard bit operations, and/or auxiliary tables.\par
{\caveat The last two are extra credit problems.}\par
\prob We are given a bag of $n$ straight line edges which someone claims represent the edges of a simple subdivision. Show how to check that he is not lying, and in the process construct the corresponding {\it quad edge} structure.\par
\prob In classical terms a polygon is called {\it monotone}, if there exists some direction such that all intersections of the polygon with lines parallel to that direction are intervals. Give an equivalent, but convolutional in spirit, definition for monotonicity. Use the new definition to derive a linear algorithm for testing if a simple polygon is monotone.\par
\vfill\eject\end