[Cyan]<PreISLCedar>Stolfi>GB>GBAMid.tex!1

\input cs445hdr
% this is midcs445.tex of February 10, 1982 6:16 PM

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

\sect{Midterm Examination, due Thursday, February 18}

{\caveat Work on this test alone. You may look at any books or journals that you wish. Please write up each problem in a separate blue-book.}\par

\prob This problem shows that there is a way to represent convex polygons which uses linear storage and which allows us to test whether two polygons intersect in logarithmic time. The representation to be used is the same as that we discussed in class for the dynamic convex hull algorithm. Each convex polygon $P$ is represented as $PĽ\inter PŘ$, where $PĽ$ is $P$ plus the ``shadow’’ it casts to the right, and $PŘ$ is defined analogously.\par

(a) [5 points] The semi-infinite polygons $PĽ$ and $PŘ$ are represented simply as a list of vertices in sorted (say decreasing) $y$-order. Show that for two convex polygons $P$ and $Q$ so represented, $P\inter Q$ is non-empty, if and only if both $PĽ\inter QŘ$ and $PŘ\inter QĽ$ are non-empty.\par

(b) [15 points] Consider now $PĽ$ and $QŘ$ as defined above, with $p$ and $q$ vertices respectively. Show that in time $O(\lg p + \lg q)$ we can decide if $PĽ$ and $QŘ$ intersect. If in fact they do, then within the above time bound we can produce a point of their intersection, otherwise we can produce a separating line.\par

\prob For two non-intersecting line segments on the plane $\alpha$ and $\beta$, $\alpha$ is said to {\it shade} $\beta$ if it is possible to translate $\alpha$ towards the right in a direction parallel to the $x$-axis, so that it intersects $\beta$.\par

(a) [5 points] Show that the shading relation is an acyclic relation (there is no cycle of segments, each shading the next). Therefore its transitive closure is a partial order on the segments.\par

(b) [15 points] Assuming that each line segment is represented by its endpoints in cartesian coordinates, find an efficient way to sort the shading relation topologically, i.e., to linearly order the line segments such that no segment shades another segment earlier in the ordering.\par

\prob In this problem we derive an algorithm for finding the maximum perimeter triangle with vertices three of $n$ given points in the plane.\par

(a) [5 points] Consider a collection of $m$ points that are the vertices of a convex polygon, and let $A$ be one of them. Show that the diameter of our point set always intersects the maximum length segment joining $A$ to another of our points (the maximum length {\it chord} rooted at $A$). Does the statement remain true if we consider two maximal chords rooted at points $A$ and $B$ instead?\par

(b) [5 points] Use this observation to develp an $O(m\lg m)$ algorithm for finding the diameter of the above collection of points.\par

(c) [5 points] Show that the vertices of the maximum perimeter triangle with vertices three of $n$ given points in the plane are vertices of the convex hull of the $n$ points.\par

(d) [10 points] By (c), we can restrict our attention to points that are the vertices of the a convex polygon, as in part (a) above. Formulate and prove a result analogous to part (a), relating the (globally) maximum perimeter triangle and a maximum perimeter triangle rooted at some particular vertex $A$.\par

(e) [15 points] Use the result of part (d) to develop an efficient algorithm for finding the maximum perimeter triangle. What is the running time of your algorithm?\par

\prob [10 points] We are given a triangulated straight line subdivision of the plane $P$, whose exterior boundary is a polygon monotone in $y$. To avoid degeneracies, we assume also that no edges of the subdivision are horizontal. Let $A$ denote the highest (in $y$) vertex, $Z$ the lowest, and $t$ the number of triangles in $P$, not counting the exterior face, if that happens to be a triangle.\par

Show that, for every integer $k$, $0 k t$, there exists a monotone chain from $A$ to $Z$ which follows edges of the subdivision, and which has exactly $k$ triangles to its left, and $t-k$ triangles to its right. Furthermore, these chains can be chosen such that if $k1̌<k2̌$, then the chains corresponding to $k1̌$ and $k2̌$ may touch, but do not cross. For a given $k$, show that such a chain can be found in time linear in the size of $P$. (Recall that for planar subdivisions, vertices, edges, and faces are all linearly related).\par

\prob [10 points] A plane is partitioned with equidistant parallel lines of distance $d$ into parallel strips of equal width. A needle of length $l$, with $l<d$, is thrown at random upon the plane. What is the probability that the needle intersects a line?\par