\documentclass[12pt]{article}
\begin{document}

\noindent 95.508 Computational Geometry.  Due on April 14, 1997.\\
For terminology and possible hints/solutions, refer to Mulmuley's book
(its on reserve in the library).  Please do cite the sources which you
are using to solve the final. Also if a group of students are
trying to solve it together, please do identify the groups.





\begin{enumerate}

\item  Consider a randomized incremental algorithm for computing the
       trapezoidal decomposition of $n$ line segments.
       We insert segment by segment and maintain the trapezoidal
       decomposition $H(N^i)$ and the conflict lists, at any stage $i$.
       In the class we defined the conflict list with respect to
       the end-points of the segments. But now we are going to change the
       definition of the conflict lists. For any trapezoid $\sigma$ 
       in $H(N^i)$, the
       conflict list is the set of (non-inserted) segments, $N-N^i$, that
       intersects the trapezoid $\sigma$.  Analyze the algorithm.
       For analysis you need to first assume that point location can be
       done, and then do the analysis and then analyze the expected cost
       of point location as well.

\item (Theorem 3.4.5, page 119) Recall the definition of configuration
      space $\pi(N)$. For any $j\le n$, let $e(j)$ denote the 
      expected size of $\pi(N^j)$, assuming that $N^j$ is a random 
      sample of $N$ if size $j$. Let $d$, a constant,
       denote the maximum degree of a configuration in $\pi(N)$. 
     Show that the expected value of the total structural change
in the randomized incremental construction is bounded by $\sum_jde(j)/j$.
Also show that  the expected  value of total conflict change is bounded
by $\sum_jd^2[(n-j)/j](e(j)/j)$. Verify your answer to Question 1 using this
result.



\item (Random Sampling theorem, Theorem 5.1.2, pp. 178) Prove the
      random sampling theorem. Let $\pi(N)$ be any configuration space
      of bounded valence. Let d be the maximum degree, and n be the size of
      N. Let $R$ be a random sample of size $r$. With probability greater
      than $1/2$, for each active configuration in $\pi(R)$, the conflict
size of $\sigma$ relative to $N$ is at most $c(n/r)\log r$, where
$c$ is a constant. More generally, fix any $c>d$. For any $s\ge r >d$, with
probablility $1-O(1/{s^{c-d}})$ the conflict size of each configuration in
$\pi(R)$ (relative to N) is less than ${c\ln s}/{(r-d)}$.

\item In the class we saw many examples of top-down sampling technique,
      e.g. the talk on polling technique. Show an example
      of bottom up sampling. A good candidate to try out will
      be skip lists. (Book has some other examples as well).


\item (furthests neighbor problem)
       Suppose we have a convex hull on $n$-vertices in the plane. 
      For each vertex, we want to know which is its furthest neighbor, i.e.
      the vertex in the convex polygon at the largest Euclidean distance.
       Give an algorithm (linear time ?)
       to solve this problem, i.e. for each vertex
       find its furthest neighbor.

\item (closest pair problem) Given a set of $n$ points in the plane, find
      the closest pair. Give an algorithm that runs in $O(n\log n)$ time,
      what is the lower bound for this problem?


\end{enumerate}

\end{document}

