\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}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Algorithmen zur Berechnung der konvexen H\"ulle}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Graham Scan}

Die Eingabe besteht aus einer Menge $P$ von $n$ Punkten in der Ebene.
Wir nehmen an, dass alle $x$-Koordinaten in $P$ verschieden sind
und dass keine drei Punkte in $P$ auf einer Geraden liegen.

Wir berechnen nur die obere konvexe H\"ulle $\text{UH}(P)$ von $P$.
Der Algorithmus f\"ur die untere H\"ulle ist analog (ersetze \texttt{isLeftOf} durch
\texttt{isRightOf})

\begin{verbatim}
  sort P by x-coordinate
  Let p[1], p[2], ..., p[n] be the sorted points
  S <- new Stack
  S.push(p[1])
  S.push(p[2])
  for i := 3 to n do
      while S.size >= 2 and p[i] is left of the line through
            the topmost two points of S do
          S.pop()
      S.push(p[i])
\end{verbatim}

Danach enth\"alt $S$ die obere konvexe H\"ulle von $P$, 
sortiert von rechts nach links.
Der Sortiervorgang ben\"otigt $O(n \log n)$ Zeit. 
Die \"ubrigen Schritte laufen in Zeit $O(n)$, da f\"ur jeden Punkt 
eine \texttt{push}-Operation und h\"ochstens eine \texttt{pop}-Operation
durchgef\"uhrt wird und da der \texttt{isLeftOf}-Test
konstante Zeit braucht.


\section{Jarvis March}

Wieder besteht die Eingabe aus einer Menge $P$ von $n$ Punkten in der Ebene, so 
dass alle $x$-Koordinaten in $P$ verschieden sind
und so dass keine drei Punkte in $P$ auf einer Geraden liegen.

\begin{verbatim}
p, p0 <- leftmost point in P
do
    q <- arbitrary point in P \ p
    for all points r in P \ {p, q} do
      if r is to the left of the directed line through p and q then
          q <- r 
      add the line segment (p,q) to the convex hull
    p <- q
while p != p0
\end{verbatim}

Jeder Durchlauf der $\texttt{do} \dots \texttt{while}$ Schleife ben\"otigt 
$O(n)$ Zeit. In jedem Durchlauf wird eine neue Kante auf der konvexen
H\"ulle gefunden. Also ist die Laufzeit O$(nh)$, wobei $h$ die Anzahl der Punkte 
(also auch die Anzahl der Kanten) auf der konvexen H\"ulle bezeichnet.
Somit ist Jarivs March ein ausgabesensitiver Algorithmus.


\section{Chans Algorithmus}

Gegeben sei wieder eine Menge $P$ von $n$ Punkten in der Ebene, so 
dass alle $x$-Koordinaten in $P$ verschieden sind
und so dass keine drei Punkte in $P$ auf einer Geraden liegen.
Au\ss{}erdem nehmen wir an, dass die Anzahl $h$ der
Punkte auf $\text{CH}(P)$ bekannt ist.
Der Algorithmus besteht aus zwei Phasen. In der ersten Phase
wird $P$ beliebig in Gruppen der Gr\"o\ss{}e $h$ aufgeteilt, und f\"ur jede Gruppe
wird die konvexe H\"ulle berechnet.

\begin{verbatim}
 1. subdivide P into n/h groups of size h
 2. for each group P[i], find CH(P[i]) in time
    O(h log h) using Graham's scan
\end{verbatim}

Die Gesamtlaufzeit f\"ur die erste Phase ist $O(n/h \cdot h \log h) = O(n \log h)$.
In der zweiten Phase werden die einzelnen Gruppen kombiniert.
Dies geschieht analog zu Jarvis's march.

\begin{verbatim}
 3. For each group P[i], let s[i] be the leftmost point.
 4. p0, p <- leftmost point of P
 5. i <- index of the group containing p
 6. do
 7.     s[i], q <- the successor of p on CH(P[i])
 8.     for j := 1 to n/h except for i do
 9.         while the successor of s[j] on CH(P[j]) is left of ps[j] do
10.            s[j] <- successor of s[j]
11.        if s[j] is to the left of pq then
12.            q <- s[j]
13.    add the line segment (p, q) to the convex hull
14.    p <- q
15.    i <- index of the group containing p
16. while p != p0
\end{verbatim}

Jeder Durchlauf der \"au\ss{}eren $\texttt{do} \dots \texttt{while}$-Schleife hat 
$O(n/h + \text{\# Durchl\"aufe der inneren \texttt{while}-Schleife})$ Schritte.
Man kann sich \"uberlegen, dass jeder Punkt nur einmal als Nachfolger in
der inneren \texttt{while}-Schleife vorkommt (d.h., jeder Punkt \texttt{s[j]} wandert nur einmal um
die jeweilige H\"ulle herum). Wie bei Jarvis's march gibt es nur $h$ Durchl\"aufe
der \"au\ss{}eren $\texttt{do} \dots \texttt{while}$ Schleife, da in jedem Durchlauf ein neuer Punkt auf $\text{CH}(P)$
entdeckt wird.  Folglich ist die Gesamtzeit $O(n)$.
Insgesamt hat Chans Algorithmus also Laufzeit $O(n \log h)$.
Um $h$ zu finden, f\"uhrt man eine superexponentielle Suche durch. Dies wird in einer \"Ubung behandelt.

\end{document}