2_Chou.tex

\documentclass{article}\usepackage{graphicx,amsmath,amsthm,amssymb}\usepackage{fullpage}\usepackage{eucal}\usepackage{graphicx}
\usepackage{color}\usepackage{tikz}\usepackage{algorithm,algorithmic}\newcommand{\question}[1]{\vspace{10pt}\noindent $\mathbf{#1}$}\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}{{~~~~~~~~~~~~~~~~~~~~~}}\newcommand{\vor}{\mathrm{Vor}}\newcommand{\CC}{\mathrm{conv}}\title{Computational Geometry Homework 2}\author{}\begin{document}  \maketitle  \section*{Administration}    Your answers should be typeset in \LaTeX\ or some equivalent and submitted as a \textbf{pdf}.    The \LaTeX\ source of these questions may be found on the course website under ``homework''.    Name your files as ``2\_\emph{your\_last\_name}.pdf'', all lowercase letters.    For example, I would call mine \textbf{2\_sheehy.pdf}.    Submission:  Use the same repository that you used for your last submission.  If you did not submit the last homework:    Create a \textbf{private} repository on github.uconn.edu and add me (userid: she13001) as a collaborator.  Name your repository ``your\_last\_name\_compgeom'' (all lowercase).    \textbf{Checkin by midnight, Nov 9: Add the pdf to the repository (but include the tex source too).  I will pull your changes and check in my comments directly on your pdf file.}  \section{Voronoi Cells and Polyhedra} % (fold)  \label{sec:voronoi_polyhedra}	Given a set of points $P \subset \R^d$, the Voronoi cell of a point $p\in P$ is the set of points closer to $p$ than any other point in $|P|$.  It is denoted	\[		\vor_P(\{p\}) = \left\{ x\in \R^d\mid\forall q\in P,\ \|x-p\|\leq\|x-q\| \right\}.	\]	Recall that a polyhedron is the intersection of a finite set of closed halfspaces.  A closed halfspace is the set of points $\{x\in \R^d \mid x^\top n \le c\}$ for a vector $n\in \R^d$ and a constant $c\in \R$.	Prove that every polyhedron is a Voronoi cell for some set.
  Hint: Pick any point in the polyhedron to be $p$.  \emph{If you get stuck, prove it for $\R^2$.}  % section voronoi_polyhedra (end)
Answer: First, we pick an arbitrary point  in the polyhedron to be $p$, and we draw the picture like this\\
\includegraphics[width=6.00in,height=2.5in]{Q1.jpg}\\
 Second, we draw the symmetric point of $p$ to each edge of the polyhedron, and we pick one of the symmetric point to be $q$, we connect $p$ and $q$, the intersection of $pq$ and the edge(hyperplane) is $k$, then $pk=kq$, we pick a point $x$($x^\top n\le c$) and connect $x$ with $q$ and $p$ respectively, thus we get $xp$ and $xq$.\\
From the question, we know that $ k^\top n=c\ $, the vector $pk=kq$, now, we need to prove that $\|x-p\|\leq\|x-q\|$, we use $\|x-p\|^2-\|x-q\|^2$ to indicate if $\|x-p\|\leq\|x-q\|$ holds. Then, we get $(x^2-2xp+p^2)-(x^2-2xq+q^2)$, after simplification, we get $(p-q)(p+q-2x)$, because $p+q=2k$, we can get$2(p-q)(k-x)$, $k-x>0$(because $ k^\top n=c$,$x^\top n<c$),$p-q<0$, so we can get $2(p-q)(k-x)<0$, Therefore, we can prove that $\|x-p\|\leq\|x-q\|$, so we satisfy the definition of the Voronoi cell, and any interior point of the polyhedron can be $x$ point and they can form a set .To any symmetric point of $p$ to any edge (halfplane) of the polyhedron, the proof above all holds. Thus we can prove that every polyhedron is a Voronoi cell for some set in $d$ dimension.\\



  \section{Bounded Voronoi Cells} % (fold)  \label{sec:voronoi_bounded}	Recall that the convex closure of a set $U\subset\R^d$ is the set of all convex combinations of the points in $U$, and is denoted	\[		\CC(U) = \left\{ {\tiny\displaystyle{\sum_{i=1}^{n}}\alpha_ip_i}\in\mathbb{R}^d\mid p_i\in U,\alpha_i\in\R_{\geq 0},\ {\tiny\displaystyle{\sum_{i=1}^n}\alpha_i}= 1 \right\}.	\]	Alternatively, we also defined the convex closure to be the intersection of all convex sets containing $U$.  A set $S$ is \emph{bounded} if there exists a radius $r$ such that $S$ is contained in the ball of radius $r$ centered at the origin.	Prove that the Voronoi cell of a point $p$ is bounded if and only if $p$ is in the interior of the convex closure of $P$.  \emph{If you get stuck, prove it for $\R^2$.}  % section voronoi_bounded (end)
  
  Answer:  There are two directions about this problem.\\
 First, we draw a picture with a convex closure.\\
 \includegraphics[width=6.00in,height=2.0in]{COLSURE.jpg}\\
 (1). point $p$ is on the edge of the convex closure,which means point $p$ is not in the interior of the convex closure, and the Voronoi cell of $p$ will be infinite.\\
 \includegraphics[width=6.00in,height=4.0in]{edge.jpg}\\
 We pick a point $x$ which $x^\top n>c$,$x^\top k>e$,$c,e$ are constant, $n,k$ are the normal vector of two hyperplanes, we can clearly know that there are infinite points like $x$, and the Voronoi cell of $p$ is infinite.\\
  (2). point $p$ is a interior point of the convex closure, and the Voronoi cell of p will be bounded.\\\includegraphics[width=6.00in,height=4.0in]{interior.jpg}\\
  Connect p with each vertex of convex closure,we find all the Deluanay Triangulation edges of point p and the convex closure, and find the Voronoi Cell of the point $p$, connect p with interceptions of each hyperplane( vertex of Voronoi Cell ), there must exist an edge st. $PD$, $PE$, $PF$ that to be the radius of the ball $S$, which contains the Voronoi Cell of point $p$.\\
  	\end{document}