\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{\ccw}{\mathrm{ccw}}
\newcommand{\CC}{\mathrm{CC}}
\newcommand{\CH}{\mathrm{CH}}
% \newcommand{\next}{\mathrm{next}}
\newcommand{\prev}{\mathrm{prev}}
\newcommand{\twin}{\mathrm{twin}}
\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 1}
\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{YourLastName}.pdf''.  
    For example, I would call mine \textbf{1\_sheehy.pdf}.
    
    \textbf{Due: Before class, Monday, September 22, 2014.}

    \textbf{Email Solutions to donald@engr.uconn.edu}
    
  \section{Dimensions} % (fold)
  \label{sec:dimensions}
  
  \question{1.1} Prove that a set of 3 points $a$, $b$, and $c$ in the plane are collinear if and only if the vectors $\vect{a}{1}$, $\vect{b}{1}$, and $\vect{c}{1}$ are linearly dependent, i.e.\ one of these points can be written as a linear combination of the other two.
  Note, you should use the equation of the line through the points to define the linear dependence.
  
    \question{1.2}
    We say that \emph{affine dimension} of a set of points is the dimension of the space of all affine combinations.
    A point is $0$-dimensional.
    A line is $1$-dimensional.
    A plane is $2$-dimensional.
    This is a little different from the notion of dimension used for vector spaces.
    It is true that a $1$-dimensional vector space is a line, but that means it can be represented as all linear combinations of a single vector.
    For a general line, we need at least two points.
    (This is the difference between vectors and points).
    Prove that the affine dimension of a set of points $p_1,\ldots, p_n\in \R^3$ is one less than the dimension of the vector space spanned by $\vect{p_1}{1},\ldots,\vect{p_n}{1}$.
    
    \question{1.3}
    Most of the time, question 1.2 means that the affine dimension of $\{p_1,\ldots, p_n\}$ is one less than the linear dimension of the same set of points when viewed as vectors.
    When is the affine dimension equal to the linear dimension?
  
  % section dimensions (end)

  \section{Convexity} % (fold)
  \label{sec:convexity}

    \question{2.1}
    In class, we gave two different definitions of the \textbf{convex closure} of a set $U\subseteq \R^d$:
    \begin{enumerate}
      \item $\CC(U)$ is the set of all convex combinations of the points of $U$.
      \item $\CC(U)$ is the intersection of all convex sets containing $U$.
    \end{enumerate}
    Prove these definitions are equivalent.
    
    \question{2.2}
    In class, we gave two different definitions to describe when a set $U\subseteq \R^d$ is \textbf{convex}:
    \begin{enumerate}
      \item $U$ is convex iff $U = \CC(U)$.
      \item $U$ is convex iff for every pair of points $a,b\in U$, and all $t\in [0,1]$, it is true that $(1-t)a + tb \in U$.
    \end{enumerate}
    Prove these definitions are equivalent.

  % section convexity (end)

  \section{Using Linear Predicates} % (fold)
  \label{sec:using_linear_predicates}
  
    \question {3.1}
    Let $\ccw(a,b,c)$ be the counterclockwise test introduced in class.  
    That is,
    \[
      \ccw(a,b,c) = \mathrm{sign} \det \left[\begin{array}{ccc} a & b & c \\ 1 & 1 & 1\end{array}\right].
    \]
    Use this predicate to write an algortihm that takes $4$ points as input and decides whether or not they are in convex position (i.e.\ every point is on the convex hull).
    \emph{Do not assume general position}.
    For this problem, we will say that the points are not in convex position if one of the points is on the line throughg two of the other points.
    Give some justification for why it is correct.
    
    \question{3.2}
    In class we saw how to check if two line segments intersect using ccw.
    In this question, you will give the ``robust'' version of that algorithm.
    Write an algorithm that takes two line segments as input (specified by the end points) and outputs true if the segments intersect and false otherwise.
    Assume that the segments are closed, so they are considered intersecting if the endpoint of one line segment lies \emph{on} the other segment.
    This will require that you check for $0$ in $\ccw$ test.
  
  % section using_linear_predicates (end)


\end{document}