\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 3}
\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 ``3\_\emph{your\_last\_name}.pdf'', all lowercase letters.  
    For example, I would call mine \textbf{1\_sheehy.pdf}.
    
    \textbf{Due by email: Before 10:00am, Friday, November 21, 2014.}

    \textbf{Email Solutions to donald@engr.uconn.edu}
    
    \section{Tutte's Algorithm} % (fold)
    \label{sec:tutte_s_algorithm}
    
      Suppose we wanted to model Tutte's Graph Drawing algorithm as a set of springs that are all pulling on one another, but the spring constants are not all the same.
      That is, for each edge $\{u,v\}\in E$, let $k_{\overline{uv}}>0$ be the spring constant for that edge.
      So, the force acting on any vertex $v$ in a drawing is
      \[
        F(v) = \sum_{u\sim v} k_{\overline{uv}} (u-v).
      \]
      Note that the condition $k_{\overline{uv}}>0$ is very important in all of the following problems.
      
      \question{1.1}
        This version of the problem can also be solved using linear algebra.
        Write down an $n\times n$ matrix $L$ such that $LP = F$ where $P$ is the $n\times 2$ matrix of coordinates for the points and $F$ is the $n\times 2$ matrix of forces.
        Express your answer by giving a formula for $L_{ii}$ and a formula for $L_{ij}$ for $i\neq j$.
    
      \question{1.2}
        Show that in any such embedding, the equilibium condition $F(v) = 0$ for interior vertices $v$ implies that 
        \[
          v = \frac{\sum_{u\sim v}k_{\overline{uv}}u}{\sum_{u\sim v}k_{\overline{uv}}}.
        \]
    
      \question{1.3}
        Show that in such an embedding, every interior vertex is in the convex closure of its neighbors.

      \question{1.4}
        Show that in such an embedding, there are monotone paths from any interior vertex $p$ to the boundary in every direction $v$.  
        That is, show that for all nonzero vectors $v\in \R^2$ and all interior vertices $p$, there is a neighbor $q$ of $p$ such that $v^\top(q-p)\ge 0$.
        Note that your proof should use linear algebra and a previous problem.
    
    
    % section tutte_s_algorithm (end)
    
    \section{Project Checkpoint} % (fold)
    \label{sec:project_checkpoint}
    
      \question{2.1}
      Create a git repository for your group. 
      Make it either private or public.
      Share it with me.
      There is an option to do this on \texttt{github.uconn.edu}.
      My username is \texttt{she13001}.
      
      \question{2.2a}
      \textbf{(Only if you are doing the project)}\\
      Give a short description of how your project will look to a user.
      Including a screen shot of work in progress would be great.
      Be sure to explain what the user will see and more importantly, what they will learn by using your project.
      Add a readme file (preferably in markdown) to appear on the github page.

      \question{2.2b}
      \textbf{(Only if you are doing the scribe notes)}\\
      Commit an outline of the notes to the git repository.
    % section project_checkpoint (end)

\end{document}