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

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

\usepackage[]{algorithm2e}

\usepackage{color}
\pagestyle{empty}

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

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

\noindent
ACKNOWLEDGE YOUR SOURCES.

\bigskip
\noindent
\begin{enumerate}

% Voronoi diagrams, Delaunay triangulations

\item{[5 marks]}
Decide on your course project.  Details about the project are now on the course web page.  For this assignment deadline, please specify:
\begin{enumerate}
\item which paper(s) you will present
\item why you chose this paper  (just a line or two)
\end{enumerate}

Note: In case you wish to change your project topic later on, just send me a revised proposal and the reason or the change.

I will ask you to choose a presentation date on Piazza.

\item{[10 marks]} Give an algorithm to compute the Voronoi diagram from the Delaunay  triangulation in linear time.  
You may assume any input format for the Delaunay triangulation, but be specific about your assumptions.
Give some detail on the low-level operations your algorithm performs (e.g., ``find the circle through three points'' is  not low-level enough).

\item{[5 marks]}  Prove that the Voronoi diagram of points in convex position is a tree.  \emph{Convex position} means that  all the points are on the convex hull.  



\end{enumerate}


\end{document}

