2_wang.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$.}\\
  For a random polyhedron, it is denoted as T=$\{x\in \R^d \mid x^\top n1 \le C1 \cap x^\top n2 \le C2 \cdots x^\top nk \le Ck \}$\\
  For a random points in the polyhedron T, every edge is a hyperplane, we create every asymmetric point $p\prime$.Thus, we got a set of points (P,$P_1\prime$,$P_2\prime$,$cdots$,$P_k\prime$),we can prove that this polyhedron is the VC of point P
  For a random points we create q($q \in P\prime$),we know q it a asymmetric points of one hyperplane (we assume its $X^\top n = C$)\\
  we can got the mid-point k between p and q.For k,$k^\top n =C$ and q-k=k-q.\\
  So, for every dimension j,($j\le d$)2$k_j$=$p_j$+$q_j$.\\
  For every X in polyhedron,\\
  $\|x-q\|^2$-$\|x-P\|^2$\\
  =$\sum\limits_{n=1}^d$ ($x_i^2$-2qixi+$q_i^2$)- ($x_i^2$-2pixi+$p_i^2$)\\
  =$\sum\limits_{n=1}^d${($q_i-p_i$)($p_i+q_i-2x_i$)}\\
  =2$\sum\limits_{n=1}^d${($q_i-p_i$)($k_i-x_i$)}\\
  =2$(k-x)^\top (q-p)$\\
  For k we know that $k\top n=c$ and $x\top n \le c$\\
  so we have $(k-x)\top n \geq 0$\\
  Also, we know that n is the normal vector of the hyperplane, we have n=$\alpha$(q-p)(for some $\alpha$, $\alpha \geq0$)\\
  So $\|x-q\|^2$-$\|x-P\|^2$==2$\alpha$$(k-x)\top n\geq 0$
  % section voronoi_polyhedra (end)
	
  \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$.}\\
  we consider this problem from the Delp Triangulating.For a set of points, we know that the Voronoi Cells is the dual of the Delp.\\
  For a set of points, we can first have its Triangulation.wwe know that convex hall is the subset of some edges after the triangulation.\\
  For every points in the convex hall,there exist a half-plane that  there is no edges in this support in this half-plane($X\top n \leq C)$The picture show as follows\\ 
   \begin{center}
  \includegraphics[width=3.00in,height=2.0in]{p1.jpg}
  \end{center}
  Since the Delp is the dual of the Voronoi, We draw a perpendicular for the hyperplane $X\top n \equiv C$, we know that every points in this perpendicular in is the Voronoi Cell of P,thus the length from points in perpendicular can be $\infty$ So it can not be bounded.\\
  Some some pint inside the triangulation, we know that there is not exist a half-plane for which every edge is in the one side of the half-plane. For a  points P, we can got a set of edge E which is connected to P, we can have a  Midperpendicular for each every, we assume that there lines intersect in some set of points(P1,P2,...PK),we define R=Max{$\|P-P_I\|$},i from i to K.
  Thus,this set of point can be bounted in to this CYCLE.  
  % section voronoi_bounded (end)
	
\end{document}