\documentclass{article}
\usepackage{graphicx,amsmath,amsthm,amssymb}
\usepackage{fullpage}
\usepackage{eucal}
\usepackage{graphicx}
\usepackage{color}
\usepackage{tikz}
\usepackage{algorithm,algorithmic}

\newcommand{\e}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}
\newcommand{\yieldstar}{\stackrel{*}{\Rightarrow}}
\newcommand{\yields}{\Rightarrow}
\newcommand{\blank}{\text{\textvisiblespace}}
\newcommand{\rep}[1]{\langle #1 \rangle}
\newcommand{\TIME}{\text{\textsc{Time}}}
\newcommand{\tab}{\hspace{30pt}}
\newcommand{\NPC}{\textsc{NP-Complete}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\vect}[2]{\bigl[\begin{smallmatrix}#1\\#2\end{smallmatrix}\bigr]}
\newcommand{\vectt}[3]{\bigl[\begin{smallmatrix}#1\\#2\\#3\end{smallmatrix}\bigr]}
\newcommand{\gap}{{~~~~~~~~~~~~~~~~~~~~~}}

\title{Computational Geometry Homework 2}
\date{}
\author{}

\begin{document}
  \maketitle
  
  \section*{Administration}
    Your answers should be typeset in LaTeX or some equivalent and submitted as a \textbf{pdf}.
    The LaTeX sourse of these questions may be found on the course website under ``homework''.
    Name your files as ``1\_\emph{your\_last\_name}.pdf'', all lowercase letters.  
    For example, I would call mine \textbf{1\_sheehy.pdf}.
    
    \textbf{Due: Before class, Wednesday, October 22, 2014.}

    \textbf{Email Solutions to donald@engr.uconn.edu}
    
  \section{The HalfEdge Data Structure} % (fold)
  \label{sec:halfedge}
  
  For this question, assume that you  have a triangulation $T$ of a point set $P$ that is represented by a halfedge data structure.
  This data structure has a HalfEdge class that supports the following operations on a half edge $h$.
  \begin{itemize}
    \item $h.v$ is the vertex at the tail of $h$.
    \item $h.next$ is the next half edge (going counterclockwise around the face).
    \item $h.prev$ is the previous half edge (going backwards around the face).
    \item $h.twin$ is the twin half edge on the other side of the edge.
  \end{itemize}
  When creating a new HalfEdge, one passes the vertex of the tail.
  
  \question{1.1}
  Given a halfedge $h$, some code below has been started to implement an edge flip.
  Finish the code by updating all the relevant pointers in the data structure.
  
  \noindent
  \textbf{flip}($h$) \{\\
  $e = h.prev$\\
  $f = h.next$\\
  $g = h.twin.prev$\\
  $i = h.twin.next$\\
  $j = \text{new HalfEdge}(g.v)$\\
  $k = \text{new HalfEdge}(e.v)$\\
  ...\\
  ...\\
  \}
  
  
  \question{1.2}
  Using the same style as the previous question, show how to implement the three-way split of the triangle represented by a HalfEdge $h$ by a new point $p$ inside that triangle.
  That is, the input to the mehtod should be a HalfEdge and a Vertex.
  % section halfedge (end)

  \section{Testing the Local Delaunay Condition} % (fold)
  \label{sec:testing_the_local_delaunay_condition}
  
    \question{2.1} 
    Suppose that you have a triangulation $T$ of a point set $P$ that is represented by a halfedge data structure as in the previous problem.
    Let $e = \overline{ab}$ be an edge of $T$ and let $c$ and $d$ be vertices of $P$ such that the triangles containing $e$ are $\triangle abc$ and  $\triangle abd$.
    Recall $e$ is locally Delaunay (LD) if it is an edge of the Delaunay triangulation $T'$ of the four points $\{a,b,c,d\}$.
    Prove that it only requires \emph{one} InCircle test to check if $e$ is LD.
    
    \question{2.2}
    Show how to implement the LD test using the HalfEdge data structure.
    That is, for a given halfedge, return true iff it is LD.
    
  % section testing_the_local_delaunay_condition (end)
  
  \section{More on Delaunay Triangulation} % (fold)
  \label{sec:more_on_delaunay_triangulation}
  
  \question{3.1} Given a set of points $P$ in general position, the Gabriel graph of $P$ is the set of edges $\overline{ab}$ such that the circle with diameter $\overline{ab}$ contains no point of $P$ in its interior.
  Prove that the Gabriel Graph is always a subset of the Delaunay triangulation.
  
  \question{3.2}
  The Euclidean Minimum Spanning Tree $T$ of a point set $P$ is the \emph{connected} graph whose vertices are the points of $P$ and such that
  \[
    \sum_{\overline{ab}\in T} \|a-b\|
  \]
  is minimized.
  Prove that the Euclidean Minimum Spanning Tree of $P$ is a subset of the Delaunay triangluation of $P$.  Again, assume $P$ is in general position.
  Hint: Consider a well-known greedy algorithm for mininum spanning trees.
  
  % section more_on_delaunay_triangulation (end)


\end{document}