\documentclass{paper}


\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator {\emst}{emst}
\DeclareMathOperator {\conv}{CH}
\DeclareMathOperator {\argmin}{argmin}
\DeclareMathOperator {\DT}{DT}
\DeclareMathOperator {\UC}{UC}
\DeclareMathOperator {\LC}{LC}

\newtheorem {theorem} {Theorem}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}


\title{Analysis of the Randomized Incremental Construction of
Convex Hulls in Space}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Clarkson's Theorem in Space}
Let $P \subseteq \R^3$ a three-dimensional $n$-point set in general 
position (i.e., no four points from $P$ lie on a common plane).
We define the set $S_{\leq k}$ of \emph{$(\leq k)$-sets} of $P$ as
\[
S_{\leq k} \eqdef \{Q \subseteq P \mid  |Q| \leq k \text{ and } 
         Q = P \cap h, h \text{ open halfspace}\}.
\]
Clarkson's theorem bounds the number of possible 
$(\leq k)$-sets.
\begin{theorem}
We have $|S_{\leq k}| = O(nk^2)$.
\end{theorem}
\begin{proof}
We assume that $3 \leq k \leq n-3$ since otherwise the theorem is
obvious.

We begin with a definition:
let $0 \leq \ell \leq k$. A pair
$(\{p, q, r\},s) \in \binom{P}{3} \times \{+,-\}$, consisting of
a set of three distinct points from $P$ and
a sign $+$ or $-$, is called \emph{$\ell$-facet} if and only if
$|P \cap h_{pqr}^s| = \ell$. Here, $h_{pqr}^+$ denotes the open
halfspace above the plane that is spanned by $p$,$q$ and
$r$ and $h_{pqr}^-$ denotes the open
halfspace below the plane spanned by $\{p,q,r\}$.
Let $L_{\leq k}$ the set of all $(\leq k)$-facets.

We have $|S_{\leq k}| = O(|L_{\leq k}|)$. Indeed, by appropriate
rotations, we can assign to each $\ell$-facet 
a constant number of $\ell$-, $(\ell+1)$- and $(\ell+2)$-sets,
and we can generate every $(\leq k)$-set in this way. 

Now, let $R \subseteq P$ be a random subset of $P$, that contains every point
$p \in P$ independently with probability $1/k$. We consider the set
$F(\conv(R))$ of facets on the convex hull of $R$, and
we bound this expectation in two ways.

On the one hand, we have
\[
\EX[|F(\conv(R))|] \leq 2\EX[|R|]) = 2n/k,
\]
as the convex hull of $R$ has at most $2|R|-4$ facets and 
each point of $P$ lies in $R$ with probability $1/k$.

Now let $X = (\{p,q,r\},s\} \in \binom{P}{3} \times \{+,-\}$ a pair
of three points from $P$ and a sign, and let
$I_{X}$ be the indicator random variable for the event that
$X$ defines a facet of $\conv(R)$ (this means that $\{p,q,r\}$
bounds a facet of $\conv(P)$ and that $h_{pqr}^{s}$ does \emph{not} contain the
polytope $\conv(R)$). Then,
\[
\EX[|F(\conv(R))|] = \sum_{(\{p, q,r\},s) \in \binom{P}{3}\times\{+,-\}}
\EX[I_{X}] \geq  \sum_{X \in L_{\leq k}} \EX[I_{X}],
\]
by linearity of expectation. For an $(\leq k)$-facet
$X$, the expectation $\EX[I_{X}]$ is the probability that
$X$ is a facet of $\conv(R)$. For this, we must have that
(i) $p, q,r \in R$; and (ii) 
$R \cap h_{pqr}^s = \emptyset$. The probability
for this is at least $k^{-3}(1-1/k)^k$, as 
$|P \cap h_{{pqr}}^s| \leq k$ and the points in  $R$
where chosen independently.

It follows that
\[
\EX[|F(\conv(R))|]  
\geq  \sum_{X \in L_{\leq k}} \EX[I_{X}]
\geq \sum_{X \in L_{\leq k}} k^{-3}(1-1/k)^k
\geq |L_{\leq k}| / 4k^3,
\]
because $k \geq 2$. Therefore, $|L_{\leq k}| \leq 4nk^2$ and
$|S_{\leq k}| \leq O(nk^2)$.
\end{proof}

\section{The $\Theta$-Series in Space}

Let $P$ a $3$-dimensional $n$-point set in general position.
In class, we saw that the total work for updating the conflict
information during the randomized incremental construction of
$\conv(P)$ is asymptotically bounded by
\[
\Theta \eqdef \sum_{(\{p,q,r\},s) \in \binom{P}{3}\times\{+,-\}} 
|P \cap h_{pqr}^s|\cdot
[\text{The face }(\{p,q,r\},s) \text{ is created during the RIC}].
\]
Here, $h_{pqr}^s$ is defined as above, and $[Z]$ is Iverson's notation:
$[Z]:=1$, if $Z$ is true, and $[Z]:=0$ otherwise.

The randomized incremental construction of $\conv(P)$ first chooses
a random permutation $\sigma$ of $P$ and inserts
the points according to the order of $\sigma$ into the hull.
We will now calculate the expected conflict change. By linearity
of expectation:
\begin{align*}
\EX_\sigma[\Theta]&=
\sum_{(\{p,q,r\},s) \in \binom{P}{3}\times\{+,-\}} 
|P \cap h_{pqr}^s|\cdot
\Pr[\text{The facet }(\{p,q,r\},s) \text{ is created during the RIC}]\\
&=
\sum_{k=1}^{n-4}\sum_{X \in L_k} k\cdot
\Pr[\text{The facet }X \text{ is created during the RIC}],
\end{align*}
where $L_k$ is the set of $k$-facets for $P$ (see above).
Since a $k$-facet $X = (\{p,q,r\},s)$ is created if and only if
the permutation $\sigma$ puts the points $p$, $q$, $r$ 
before the $k$ points in $P \cap h_{pqr}^s$, we have
\[
\Pr[\text{The facet }X \text{ is created during the RIC}] = 
\frac{3!k!}{(k+3)!} = \frac{6}{(k+1)(k+2)(k+3)}.
\]
Hence,
\[
\EX_\sigma[\Theta] = 
\sum_{k=1}^{n-4}\sum_{X \in L_k} 
\frac{6k}{(k+1)(k+2)(k+3)} \leq 
\sum_{k=1}^{n-4} \frac{6|L_k|}{k^2}.
\]
We write $|L_k| = |L_{\leq k}| - |L_{\leq(k-1)}|$, where 
$L_{\leq k}$ denotes the set of $\ell$-facets of $P$ for $0 \leq \ell \leq k$. 
Using summation by parts,
\begin{multline*}
\EX_\sigma[\Theta] \leq 
\sum_{k=1}^{n-4} \frac{6}{k^2}\Bigl(|L_{\leq k}| - |L_{\leq(k-1)}|\Bigr)\\
= \frac{6}{(n-3)^2}|L_{\leq(n-4)}| - 6|L_{\leq0}| +
\sum_{k=1}^{n-4} |L_{\leq k}| \Bigl(\frac{6}{k^2}-\frac{6}{(k+1)^2}\Bigr)
\leq O(n) + \sum_{k=1}^{n-4} \frac{18 |L_{\leq k}|}{k^3},
\end{multline*}
since $|L_{\leq(n-4)}| = O(n^3)$, $|L_{\leq 0}| = O(n)$ and
\[
\frac{6}{k^2}-\frac{6}{(k+1)^2} = 
\frac{12k+6}{k^2(k+1)^2} \leq \frac{18}{k^3}.
\]
By Clarkson's Theorem, we have $|L_{\leq k}| = O(nk^2)$, so
\[
\EX_\sigma[\Theta] =
O\Bigl(\sum_{k=1}^{n-4} \frac{nk^2}{k^3}\Bigr) = 
O\Bigl(n \cdot \sum_{k=1}^{n-4} \frac{1}{k} \Bigr) = O(n \log n).
\]
The expected conflict change, and hence the expected running time
for the randomized incremental construction of convex hulls in
$\R^3$, is $O(n \log n)$.
\end{document}