2_tan.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{Yiyun Tan}

\begin{document}
  \maketitle

  \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$.}\\
  
  Solution: \\
  According to above, a polyhedron can be denoted as T=$\{x\in \R^d \mid x^\top $n_1$ \le $C_1$ \cap x^\top $n_2$ \le $C_2$ \cdots x^\top $n_k$ \le $C_k$ \}$\\$
  Pick a point in the polyhedron to be p.
  Suppose there is a set of points q in the same polyhedron as the point p, and in the set there are n points:$q_1$,$q_2$...$q_n$\\
  So the distances between p and the set of q is
   $\|x-q\|^2$-$\|x-P\|^2$
  =$\sum\limits_{1}^n$ ($x_i^2$-2$q_ix_i+$q_i^2$)- ($x_i^2$-2$p_ix_i$+$p_i^2$)
  =$\sum\limits_{1}^n${($p_i-q_i$)($2x_i-p_i-q_i$)}\\
  Create every asymmetric point $p\prime$ of p through each edge of the polyhedron T.
  Then there is a new set of points ($P$,$P_1\prime$,$P_2\prime$...$P_k\prime$),we can prove that this polyhedron is the VC of point P.
  So $\sum\limits_{1}^n${($p_i-q_i$)($2x_i-p_i-q_i$)}
  =2$\sum\limits_{1}^n${($q_i-p_i$)($k_i-x_i$)}
  =2$(k-x)^\top (q-p)$\\
  For an arbitrary point p, create the point q($q \in P\prime$). Since q is a asymmetric point of one hyperplane, we assume it is $X^\top n = C$). Then we get the mid-point k between p and q. For $k$, $k^\top n =C$ and q-k=k-q.\\
  And for amplification，every dimension j($j\le d$)，2$k_j$=$p_j$+$q_j$.\\
  Also $k\top n=c$ and $x\top n \le c$， then $(k-x)\top n \geq 0$,  n=$\alpha$(q-p)(for some $\alpha$, $\alpha \geq0$)\\
  So $\|x-q\|^2$-$\|x-P\|^2$=2$\alpha$$(k-x)\top n\geq 0$. \\
  Q.E.D. the above means every polyhedron is a Voronoi cell for some set. 
  % 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$.}\\
  
  Solution:\\
  Think about the Delaunay triangulation from class. As for a set of points, we know that the Voronoi Cells is the dual of Delaunay triangulation. Firstly we can have its triangulation, and the convex hull is the subset of some edges after the triangulation of the original set.\\
  For each point in a convex hull, there exists a half-plane that no edge in this support in this half-plane($X\top n \leq C)$. 
  Since the DelP is the dual of the Voronoi, draw a perpendicular for the hyperplane $X\top n \equiv C$. Since every point in this perpendicular in is the Voronoi Cell of P, the points in perpendicular cannot be bounded\\
  Also there doesn't exist such a half-plane, whose each edge is in the one side of the hyperplane. For an arbitrary point P in the perpendicular, there is a set of edges E which connected to point P, then make mid-perpendicular for each edge. Consider those intersects are composed a set ($P_1$,$P_2$...$P_k$), we define Max{$\|P-P_i\|$}, where i is from 1 to k.
  According to above, then the set of point can be bounded in a convex closure. \\
  Q.E.D. the Voronoi cell of a point $p$ is bounded if and only if $p$ is in the interior of the convex closure of $P$.
  % section voronoi_bounded (end)
	
\end{document}