\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amsopn}
\usepackage{graphicx}
\usepackage{color}
\usepackage{verbatim}
\usepackage{setspace}
\usepackage{gensymb}
\usepackage{float}
\usepackage[normalem]{ulem}
%\usepackage[dvips,bookmarks=false,colorlinks,urlcolor=blue,pdftitle={
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{mathdefs}

\def\bx{{\bf x}}
\def\by{{\bf y}}
\def\bz{{\bf z}}
\def\V{{\bf V}}
\def\vl{{\bf l}}
\def\vm{{\bf m}}
\def\mS{{\bf S}}
\def\mT{{\bf T}}
\def\mH{{\bf H}}
\def\mA{{\bf A}}
\def\mM{{\bf M}}
\def\mP{{\bf P}}
\def\tx{{\tilde{\bf x}}}
\def\ta{{\tilde{\bf a}}}
\def\tb{{\tilde{\bf b}}}
\def\tc{{\tilde{\bf c}}}
\def\hn{{\bf \hat{n}}}
\def\hv{{\bf \hat{v}}}
\def\hh{{\bf \hat{h}}}
\def\vh{{\bf h}}
\def\vs{{\bf s}}
\def\hs{{\bf \hat{s}}}
\newcommand{\Ev}{\mathbf{E}}
\newcommand{\Fv}{\mathbf{F}}

\usepackage[bookmarks=false,colorlinks,urlcolor=blue,pdftitle={Take-home Quiz 8},pdfauthor={Matthew O'Toole}]{hyperref}

\begin{document}

\begin{centering}
	{\large 16-385 Computer Vision, Fall 2020\\}
	\vspace{2ex}
	{\LARGE Take-home Quiz 8\\}
	\vspace{2ex}
	{\large Due Date: Monday November 10, 2020 23:59\\}
\end{centering}

\bigskip

\section*{Question 1}

Let us assume that we use the nearest-neighbor (NN) algorith for classification of $d$-dimensional vectors into one of labels $\curly{1,\dots,L}$, together with the \emph{Euclidean distance} metric and a set of labeled training data points $\bx_n \in \R^d, n\in\curly{1,\dots,N}$. The training data points create a segmentation of the $\R^d$ space into $N$ so-called \emph{Voronoi cells}: For each $n\in\curly{1,\dots,N}$, the Voronoi cell $\V_n\subset\R^d$ is the subset of $\R^d$ such that any point $\by\in\V_n$ has training point $\bx_n$ as its nearest neighbor, and thus $\by$ is classified as having the same label as $\bx_n$. We can ``color'' each such cell by the label of the training point $\bx_n$ it is associated with. Figure~\ref{fig:voronoi} shows two Voronoi segmentation examples, for the cases $d=2,3$ and $L=2$.

Prove that all Voronoi cells are convex: this means that, if $\by$ and $\bz$ belong to the same Voronoi cell, $\by,\bz\in\V_n$, then so does any point on the linear segment connecting $\by$ and $\bz$.  In mathematical terms, for all $\by,\bz\in\V_n$, it holds that $\alpha \by + (1-\alpha)\bz \in \V_n$ for all $0 \leq \alpha \leq 1$.

\emph{Hint:} It will be helpful to consider the case of two dimensions ($d=2$) and two training data points ($N=2$). Under these assumptions, the problem should reduce to a simple Euclidean geometry exercise. Once you have worked out this case, you can generalize to the case of two dimensions ($d=2$) and multiple data points ($N\ge 2$). Finally, you can extend this to the full case of any number of dimensions ($d\ge 2)$ and multiple data points ($N\ge 2$).

\begin{figure}[hbtp]
\begin{center}
\includegraphics[width=0.6\textwidth]{figures/voronoi2}
\caption{Example Voronoi segmentations induced by the nearest-neighbor algorithm, in two (left) and three (right) dimensions.}\label{fig:voronoi}
\end{center}
\end{figure}

\section*{Instructions}

\begin{enumerate}
    \item \textbf{Integrity and collaboration:} Students are encouraged to work
    in groups but each student must submit their own work. If you work as a
    group, include the names of your collaborators in your write up. Plagiarism
    is strongly prohibited and may lead to failure of this course.

    \item \textbf{Questions:} If you have any questions, please look at Piazza
    first. Other students may have encountered the same problem, and it may be solved
    already. If not, post your question on the discussion board. Teaching staff will
    respond as soon as possible.

    \item \textbf{Write-up:} Your write-up should be typeset in \LaTeX and should consist of your answers to the theory questions. Please note that we
    \textbf{\color{red}do not} accept handwritten scans for your write-up in quizzes.

    \item \textbf{Submission:} Your submission for this take-home quiz should be a
    PDF file, \texttt{<andrew-id.pdf>}, with your write-up. \textbf{\color{red}Please do not submit ZIP files.}
\end{enumerate}

\end{document}
