\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{hyperref}
 \usepackage{amsmath,amssymb,color,amsthm,graphicx}

\usepackage[]{algorithm2e}

\usepackage{xcolor}
\pagestyle{empty}

\begin{document}
\begin{center}
CS 763 Fall 2022 \hfill due Wednesday November 2\\
{A.~Lubiw \hfill \quad}
\end{center}

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

\noindent
ACKNOWLEDGE YOUR SOURCES.

\bigskip
\noindent
\begin{enumerate}

\item{[5 marks]}  {\color{red} Please send your answer to this question as text in an email message}, so I can easily and quickly approve or make suggestions. 

Decide on your course project.  Details about the project are now on the course web page.  Please specify:
\begin{enumerate}
\item which paper(s) you will present
\item why you chose this paper  (just a line or two)
\end{enumerate}

{\bf 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]
The {\it farthest point Voronoi diagram\/} of point set $P = \{p_1, \ldots,
p_n\}$, in the plane, is the locus of points equally far from
more than one site of $P$.  More precisely, define the farthest region for
$p_i$ to be $\{x \in R^2 \colon d(x,p_i) \ge d(x, p_j), \forall p_j \ne p_i\}$.

\begin{enumerate}

\item{} Prove that the farthest region for $p_i$ is convex.
\item{} Characterize the sites with unbounded farthest regions.
\item{} Characterize the sites with empty regions.
\end{enumerate}

\item{[5 marks]}
Show how to compute the Gabriel graph from the Delaunay triangulation in linear time.

\item{[10 marks]}
Give an $O(n \log n)$ time algorithm for the following problem.  
The input is a set $S$ of $n$ points in the plane and a natural number $k$.  Partition $S$ into a set of $k$ disjoint subsets $S_1, S_2, \ldots, S_k$ that are ``as far from each other as possible''---to be precise, you must
maximize the minimum distance between two point from different subsets.
Keep your algorithm high-level.  You may use algorithms and results from class.  Make sure you prove that your approach is correct.

HINT: this whole assignment is about Voronoi diagrams and Delaunay triangulations.  



\end{enumerate}

\end{document}
