\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\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{Clarkson's Theorem}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle
Let $P \subseteq \R^2$ be a planar point set of size $n$.
The set $S_{\leq k}$ of \emph{$(\leq k)$-sets} of $P$ is defined as
\[
S_{\leq k} \eqdef \{Q \subseteq P \mid  |Q| \leq k \text{ and } 
         Q = P \cap h, h \text{ open halfplane}\}.
\]
Clarkson's theorem gives an upper bound on the number of possible 
$(\leq k)$-sets.
\begin{theorem}
We have $|S_{\leq k}| = O(nk)$.
\end{theorem}
\begin{proof}
We may assume that $2 \leq k \leq n-2$, since otherwise the
theorem clearly holds.

We begin with a definition:
Let $0 \leq \ell \leq k$. A pair $(p, q) \in P^2$ 
of distinct points in $P$ is called \emph{$\ell$-edge} if and only if
$|P \cap h_{\overrightarrow{pq}}^+| = \ell$. Here,
$h_{\overrightarrow{pq}}^+$ denotes the open halfplane to the left of
the oriented line $\overrightarrow{pq}$. Let $L_{\leq k}$ be the set of
all $(\leq k)$-edges.

We have $|S_{\leq k}| \leq 2 |L_{\leq k}|$. We can
assign to each $\ell$-edge
$(p, q)$ one $\ell$- and one $(\ell+1)$-set, 
namely the $\ell$-set $P \cap h_{\overrightarrow{pq}}$, and
the $(\ell+1)$-set that is cut off from $P$ after slightly rotating
$\overrightarrow{pq}$ clockwise around
$p$. Every  $(\leq k)$-set $Q$ can be obtained this way.
To see this,  take a line $g$ that bounds the halfplane 
defining $Q$. Translate $g$ away from $Q$ until it hits a point from
$P$, then  rotate $g$ counterclockwise until it hits another point from
$P$. 

Let $R \subseteq P$  a random subset of $P$ containing
each point $p \in P$ independently with probability $1/k$. We consider
the set $E(\conv(R))$ of the edges on the convex hull of $R$, and 
we bound the size of $E(\conv(R))$ in two different ways.

On the one hand, we have
\[
\EX[|E(\conv(R))|] \leq \EX[|R|] = n/k,
\]
since the convex hull of $R$ has at most $|R|$ edges, and
each point from $P$ was chosen with probability $1/k$.

Now let $(p, q) \in P^2$ be a pair of distinct points in $P$, and
let $I_{(p, q)}$ be the indicator random variable for the event that
$(p, q)$ defines a (clockwise) edge on $\conv(R)$. Then,
\[
\EX[|E(\conv(R))|] = \sum_{(p, q) \in P^2} \EX[I_{(p, q)}]
\geq  \sum_{(p, q) \in L_{\leq k}} \EX[I_{(p, q)}],
\]
by linearity of expectation. For a $(\leq k)$-edge
$(p, q)$ we have that $\EX[I_{(p, q)}]$ is precisely the probability of
the event $(p, q) \in E(\conv(R))$. For this event to happen, we must have
(i) $p, q \in R$; and (ii) 
$R \cap h_{\overrightarrow{pq}}^+ = \emptyset$. The probability for this
is at least $k^{-2}(1-1/k)^k$, since 
$|P \cap h_{\overrightarrow{pq}}^+| \leq k$ and since the points in $R$
were chosen independently.

It follows that
\[
\EX[|E(\conv(R))|]  
\geq  \sum_{(p, q) \in L_{\leq k}} \EX[I_{(p, q)}]
\geq \sum_{(p, q) \in L_{\leq k}} k^{-2}(1-1/k)^k
\geq |L_{\leq k}| / 4k^2,
\]
as $k \geq 2$. Hence, $|L_{\leq k}| \leq 4nk$ and
$|S_{\leq k}| \leq 8nk$.
\end{proof}
\end{document}