\documentclass[11pt,epsf]{article}
\parindent 0in
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{epsfig}

\newcommand{\handout}[5]{
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.409 The Behavior of Algorithms in Practice} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\beginproofof}[1]{\medskip\noindent{\bf Proof of #1.~}}
\newcommand{\finishproof}{\hspace{0.2ex}\rule{1ex}{1ex}}
\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer: #3}{Scribe: #4}{Lecture #1}}
\newenvironment{proofof}[1]{\beginproofof{#1}}{\unskip\nolinebreak
\finishproof\par\medskip}

\newcommand{\Kappa}{\kappa}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}

\setlength{\topmargin}{-0.50in}
\setlength{\textheight}{8.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{-0.0in}
\setlength{\textwidth}{6in}
\addtolength{\parskip}{2pt}
\addtolength{\itemsep}{0.1in}
\parskip 1.5ex

\renewcommand{\baselinestretch}{1.25}

\begin{document}

\newif\ifdimspec
\def\figsize#1{\dimspecfalse \checkdim#1\end
\ifdimspec
  \def\figureWidth{#1}%
\else
  \def\figureWidth{#1 in}\fi}
\def\checkdim#1{\ifx#1\end \let\next=\relax
  \else \ifcat#1a \dimspectrue \fi \let\next=\checkdim\fi \next}
\newcommand{\lblcaption  }[2]{\caption{#2\label {#1}}}
\newcommand{\Figuresized }[3]{\begin{figure}[htbp]
  \begin{center}
  \mbox{\figsize{#3}\epsfig{file=#1.eps,width=\figureWidth}}
  \end{center}
  \lblcaption{#1}{#2}
  \end{figure}}
\newcommand\E{\mathop{\rm E}}
\newcommand\gr{\stackrel{\phantom{h}}}
\newcommand \dd[1]{\mathop{d #1}}
\lecture{15/16}{4/18/02 and 4/23/02}{Dan Spielman}{Mikhail Alekhnovitch}

Let $a_1,...,a_n$ be independent random gaussian points in the plane with variance $1$.
Today lecture is devoted to the following question: what is the 
expected size of their convex hull?
%Let $CH_n$ be the random variables corresponding to the convex hull of $a_1,...,a_n$, denote
%by $V_n$ the number of vertices in $H_n$.

\begin{theorem}[Renyi-Salanke]
$$\E\limits_{a_1,...,a_n}[\mbox{\rm size of C.H.}] = \Theta(\sqrt{\lg n}).$$
\end{theorem}

In this lecture we will prove a weaker bound $O(\lg^2 n).$ First we notice, that

$$\Pr[\bar
o\not\in \mbox{C.H.}]\le \left(\frac 3 4\right)^{\frac n 3}.$$

This is because the probability that $\bar o\not\in \mbox{C.H.}$ 
of three points is exactly $3/4$, so we can
divide all points into $n/3$ groups of $3$, and each group covers $o$ 
with probability $1/4$.
Thus, with exponentially high probability 
$\bar o\in C.H.$ so we can assume for the rest of the
lecture that this is always the case.

For a vector $z$ consider the edge $(a_j,a_k)$ of the convex hull that crosses
$z$ clockwise. Denote

$$P_z(\epsilon) = \Pr [ang(z\bar oa_k))<\epsilon].$$

Then clearly

$$\E[\mbox{size of C.H.}]
\le \lim_{\epsilon\to 0} \frac {2\pi}\epsilon P_z(\epsilon) + 
n\left(\frac 3 4\right)^{\frac n 3}.
$$

Denote by $CH_{j,k}$ the event that $(a_j,a_k)$ is an edge of $CH(a_1,...,a_n)$ 
and other points lie on the origin side of the line $a_ja_k$.
For a fixed vector $z$, $Cross_{jk}$ is the event that the edge 
$(a_j, a_k)$ crosses $z$ clockwise.
\Figuresized{f1}{}{2}

$$P_z(\epsilon) = \sum_{j,k}\Pr\left[CH_{j,k}\gr\land Cross_{j,k}\right]\cdot 
\Pr\left[ang(z\bar oa_k)\gr<\epsilon|CH_{j,k}\land Cross_{j,k}\right] =$$
$$=\Pr\left[ang(z\bar oa_k)\gr<\epsilon|CH_{j,k}\land Cross_{j,k}\right]$$
for any choice of $j$ and $k$ (the latter equation follows because of the symmetry).
 Assume that $(a_j,a_k)$ crosses $z$. It will
be convenient to choose the coordinates $\theta,t,l,r$ instead of $a_j, a_k$
(see figure~\ref{f1}). Let $\alpha = ang(zoa_k).$ Then the probability $P_z(\epsilon)$
can be expressed as:

$$
\frac
{\int\limits_{t,\theta} \left( \int\limits_{i\not=j,k} [CH_{j,k}]\right) \cdot
\int\limits_{l,r\ge 0} \left([\alpha\gr<\epsilon]\right) (l+r)sin(\theta) \mu(a_j)\mu(a_k)
\dd \theta\dd t \dd l \dd r}
{\int\limits_{t,\theta}\left( \int\limits_{i\not=j,k} [CH_{j,k}]\right) \cdot
\int\limits_{l,r\ge 0}(l+r)sin(\theta) \mu(a_j)\mu(a_k)
\dd \theta\dd t \dd l \dd r}
$$

We need the following claim that estimates the maximal norm of $n$ gaussian points in the plane.
\begin{claim}
$$\Pr\left[\max_i ||a_i||\gr>\sqrt{8\lg n}\right]< \frac 1 n.$$
\end{claim}

In the assumption of the claim, we can bound $t\le \sqrt{8\lg n};$ $r,l\le 2\sqrt{8\lg n}$.
Once again we can assume that this is always the case (it can change the expectation at
most by $1$). 
When $\alpha$ is sufficiently small,
$$\alpha>\frac 1 2\tan(\alpha) = \frac 1 2\cdot \frac {r\sin(\theta)}
{t+r \cos(\theta)} \ge \frac {r\sin(\theta)}{6 \sqrt{8\lg n}}.$$

Thus 

$$\E[\mbox{size of C.H.}]\le \lim_{\epsilon\to 0} 
\frac{2\pi}{\epsilon} P_z(\epsilon)+ 
n\left(\frac 3 4\right)^{\frac n 3}
\le 
\lim_{\epsilon\to 0}\frac{2\pi}{\epsilon}
\Pr
\left[ \frac {r\sin(\theta)}{6 \sqrt{8\lg n}}<\epsilon \right] + 
n\left(\frac 3 4\right)^{\frac n 3} + 1.$$

We estimate the latter probability using the Combination Lemma from Lecture~19.
Namely, we show that 

$\Pr[r<\epsilon]<O(\sqrt {\lg n} \cdot \epsilon)$

$\Pr[\sin(\theta)<\epsilon] = O(\lg n \cdot \epsilon^2).$

Thus, the following two lemmas imply the theorem:

\begin{lemma}\label{l1}
$\forall t\le \sqrt{8\lg n}$ 

\begin{equation}\label{int1}
\frac{\int\limits_{r\ge 0}[r<\epsilon](l+r)\mu(a_k) \dd r}
{\int\limits_{r\ge 0} (l+r)\mu(a_k) \dd r}\le O(\sqrt{\lg n}\cdot \epsilon)
%e^2\sqrt{8\lg n}\cdot \epsilon
\end{equation}

\end{lemma}

\begin{lemma}\label{l2}$\forall t\le \sqrt{8\lg n},$ $l,r\le 2\sqrt{8\lg n}$

\begin{equation}\label{int2}
\frac
{
\int\limits_\theta [\sin(\theta)\le\epsilon] 
\left(\int\limits_{i\not=j,k}[CH_{j,k}]\right)\sin(\theta)\mu(a_j)\mu(a_k)}
{
\int\limits_\theta  
\left(\int\limits_{i\not=j,k}[CH_{j,k}]\right)\sin(\theta)\mu(a_j)\mu(a_k)
}
\le O((\lg n \cdot \epsilon)^2)
%e^4 8(\lg n \cdot \epsilon)^2
\end{equation}

\end{lemma}

\begin{proofof}{Lemma~\ref{l1}}

Let $u_\theta$ be a unit vector along $a_j a_k$ (and assume that $z$ is a unit vector). 
Look at 
$$\mu(a_k)= \mu(tz+r u_\theta)=e^{-\frac{d^2}2} e^{-\frac{(s+r)^2}2},$$ where $d$ and $s$ are defined
at figure~\ref{f2}.

\Figuresized{f2}{}{2}

\begin{proposition}\label{p1}
For $s>1,$ $r\le \frac 1 s$

$$
\frac{e^{-\frac {s^2}2}}{e^{-\frac {(s+r)^2}2}}\le e^2
$$
\end{proposition}

As a corollary, for $0<r_1<r_2<\frac 1 {\sqrt{8\lg n}}$ holds

$$ \frac{\mu(tz+r_1 u_{\theta})(l+r_1)}{\mu(tz+r_2 u_\theta)(l+r_2)}\le e^2.$$

\begin{proposition}\label{p2}
Let $f$ be s.t. for $0<x_1< x_2<K$ and $\frac {f(x_1)}{f(x_2)}<c$. Then

$$\frac{\int\limits_0^\epsilon f(x) \dd x }{\int\limits_0^K f(x) \dd x}\le \frac {\epsilon c}K.$$
\end{proposition}

\begin{proof}
One can split the interval $[0,K]$ into $\frac K \epsilon$ subintervals of length $\epsilon$.
The integral of $f$ on each subinterval is lower bounded by $c^{-1}\int\limits_0^\epsilon f(x) \dd x,$
thus
$\int\limits_0^K f(x)\dd x \ge \frac K \epsilon c^{-1}\int\limits_0^\epsilon f(x).$
\end{proof}

It is sufficient to choose $K=1/\sqrt{8\lg n}$ to finish the proof of Lemma~\ref{l1}.
\end{proofof}

\begin{proofof}{Lemma~\ref{l2}}

Let

$$g(\theta) = \underbrace{\left( \int\limits_a [CH_{j,k}] \prod \mu(a_i)
\right)}_{g_1(\theta)} \sin(\theta) \underbrace 
{ \mu(tz+r u_\theta) \mu(tz-l u_\theta)}_{g_2(\theta)} $$


In order to estimate the ratio~(\ref{int2}) it will be sufficient to confine
ourselves to $0<\theta<\frac 1 {16 \lg n}$ in the denominator.
For $0<\theta_1<\theta_2<\frac \pi 2$ holds

$$\frac {g_1(\theta_1)}{g_1(\theta_2)}\le 1.$$

To see this, notice that $g_1(\theta)$ is the probability of the rest of the points
$a_i$ lying on the origin side of the line $a_ja_k$. This probability decreases
when the distance of the line $a_j a_k$ to $\bar o$ decreases, thus $g_1(\theta)$ is monotone.

As in Proposition~\ref{p1}, for $t<\sqrt{8\lg n}$; $l,r<2\sqrt{8\lg n}$;
$0<\theta_1<\theta_2<\frac 1 {16\lg n}$ holds

$$\frac{\mu(tz + r u_{\theta_1})}{\mu(tz+r u_{\theta_2})}<e^2,$$

which implies for  $0<\theta_1<\theta_2<\frac 1 {16 \lg n}$ 

$$\frac{g_2(\theta_1)} {g_2(\theta_2)}\le e^2.$$

Finally, for small values of 
$\theta$, $\sin(\theta)\sim \theta$, 
so
for $0<\theta_1<\theta_2<\frac 1 {16 \lg n}$

$$\frac {g(\theta_1) }{g(\theta_2)}\le 2e^4 \frac{\theta_1}{\theta_2}.$$

The following fact is the analog of Proposition~\ref{p2}:

\begin{proposition}
If for $x_1<x_2$ $\frac{f(x_1)}{f(x_2)}\le c \frac {x_1}{x_2}$ then 

$$\frac {\int\limits_0^\epsilon f(x) \dd x} {\int\limits_0^K f(x)\dd x}\le 4 c  
\left(\frac \epsilon K\right)^2$$
\end{proposition}

It is left to set $K=\frac 1 {16 \lg n}$. The lemma is proven.
\end{proofof}

At the end we justify the change of variables $(a_j,a_k)\to (l,r,t,\theta)$
that we made in the proof and compute the Jacobian of this transform.
Let $a=a_j$ and $b=a_k$ be two points in ${\bf R}^2,$ specified by four parameters
$l,r,h,\theta$ as shown on figure~\ref{f1}.
By the straightforward calculation,

$a_x = l\sin (\theta)$

$a_y = t - l\cos (\theta)$

$b_x = r \sin(\theta)$

$b_y = t + r\cos(\theta)$

The Jacobi matrix 

$$J = \begin{array}{cc}
\partial a_x\ \quad \ \ \ \ \ \partial a_y\quad \ \  \ \ \  \partial b_x \quad  \ \ \ \ \
\ \partial b_y
& \\
\left(\begin{array}{cccc}
0 &0 & \sin(\theta) &\cos(\theta)\\
\sin(\theta) & -\cos(\theta) & 0 &0\\
l\cos(\theta) & l\sin(\theta) & r\cos(\theta) &-r\sin(\theta)\\
0 &1 &0 &1
\end{array}\right)
 &
\begin{array}c
\partial r\\
\partial l\\
\partial \theta\\
\partial t
\end{array}
\end{array}
$$

and the Jacobian
$$|\det J| = (l+r) \sin(\theta),$$
hence
$$\dd a \dd b = (l+r)\sin(\theta)\dd r\dd l \dd \theta \dd t.$$
\end{document}












