\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{Triangulierung eines $y$-monotonen Polylgons}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

Die Eingabe ist ein einfaches $y$-monotnes Polygon $P$ in allgemeiner 
Lage, d.h., die $y$-Koordinaten aller Ecken von $P$ sind 
paarweise verschieden. Die Ausgabe besteht aus einer Menge von  
Diagonalen, die $P$ triangulieren. Der Algorithmus arbeitet
folgenderma\ss{}en.

\begin{verbatim}
  Erstelle eine Liste aller Ecken, von oben nach unten nach 
  y-Koordinate sortiert  (u[1], u[2], u[3], ... , u[n]).

  S <- new Stack() 
  // S.top() oberstes Element auf dem Stack
  // S.secondTop() zweitoberstes Element auf dem Stack
  S.push(u[1]); S.push(u[2])

  for i := 3 to n-1 do
      if u[i] und S.top() sind auf verschiedenen Seiten von P then
          while S.size() > 1 do
              u <- S.pop()
              Erzeuge eine Diagonale zwischen u[i] und u 
          S.pop(); S.push(u[i-1]); S.push(u[i]);
      else
          while S.size() > 1 AND 
                  die Kante u[i]-S.secondTop() liegt unter 
                  der Dreierkette u[i]-S.top()-S.secondTop() do
              S.pop()
              Erzeuge eine Diagonale zwischen u[i] und S.top() 
          S.push(u[i])
  S.pop()
  while S.size() > 1 do 
      u <- S.pop()
      Erzeuge eine Diagonale zwischen u[n] und u 
\end{verbatim}

Die Laufzeit f\"ur jeden Durchlauf der \texttt{for}-Schleife
ist $O(1 + \text{Anzahl der $S.\texttt{pop}()$ Operationen})$. 
In jedem Durchlauf der \texttt{for}-Schleife
werden nur konstant viele Elemente auf $S$ gepusht. Jedes
Element, das gepopt wird, wurde vorher gepusht. Also ist
die Gesamtlaufzeit $O(n)$.
\end{document}