\documentclass[11pt]{article}
\usepackage{fullpage}

\usepackage{amsmath,amssymb,color,amsthm,graphicx}

\usepackage{xcolor}
\pagestyle{empty}

\begin{document}
\begin{center}
CS 763 Fall 2020 \hfill due Thursday October 8\\
{A.~Lubiw \hfill \quad}
\end{center}

\begin{center}
\large\bf ASSIGNMENT 3
\end{center}

\noindent
ACKNOWLEDGE YOUR SOURCES.


This assignment has more questions, but several of them are really exercises.

\begin{enumerate}

\item{[5 marks]}
Find an example where the incremental 3D convex hull algorithm takes $\Theta(n^2)$ time.
(This was suggested as an exercise in Lecture 6.)

\item{[10 marks]} 
The \emph{sharpness} of a vertex $v$ of a convex polyhedron in $\mathbb{R}^3$ is $2\pi$ minus the sum of the face angles at  $v$.  For example, a vertex of a cube has 3 face angles each of $\pi /2$, so its sharpness is $2\pi - 3\pi /2  = \pi/2$.
Prove that the sum of the sharpness of all the vertices of a convex polyhedron is $4\pi$.

You will need Euler's formula and one other ingredient.

\item{[5 marks]} 
Suppose you are given $n$ red points and $m$ blue points in the plane.  You want to know if there is a line separating the red points from the blue points. 

\begin{enumerate} 
\item Express this as a linear programming problem in 2D (i.e., with two variables).  You may assume that no two given points are at the same $x$ coordinate---this implies that if there is a separating line then there is a separating line that is not vertical.
\item What does this problem become in the dual? (Just state the dual problem.)
\end{enumerate}

\item{[5 marks]}  
Consider the following randomized algorithm to find the minimum of $n$ distinct integers.  
Take a random order $x_1, \ldots, x_n$ of the input numbers.  Set $m = \infty$.  For $i=1 \ldots n$, if $x_i <m$ then update $m$ to $x_i$.

Use backwards analysis to argue that the expected number of times you update $m$  is $O(\log n)$.  (You may use without proof the fact that the Harmonic numbers grow as $O(\log n)$.) 

 
\end{enumerate}

\end{document}
