\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{Sweepline-Algorithmen}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Bentley-Ottman Algorithmus}

Die Eingabe besteht aus einer Folge $\texttt{s[1]}, 
\texttt{s[2]}, \dots, \texttt{s[n]}$ von Strecken  
in ``allgemeiner Lage'', die jeweils durch den
Start- und Endpunkt repr\"asentiert werden. 
Dabei liegt jeder Startpunkt links vom jeweiligen Endpunkt.
Gesucht ist die Menge alle paarweisen Schnittpunkte der 
Strecken, sortiert von links nach rechts.

Der Algorithmus benutzt zwei Datenstrukturen: den \emph{Event Point
Schedule} (EPS) und den \emph{Sweepline Status} (SLS). 
Beim Event Point Schedule handelt es sich um eine 
Priorit\"atswarteschlange, welche die
Ereignispunkte von links nach rechts sortiert enth\"alt.
Der Sweepine Status ist ein geordnetes W\"orterbuch, das die Strecken,
welche die aktuelle Sweepline schneiden, von oben nach unten sortiert
enth\"alt (wie implementiert man das in Java?)
Der Algorithmus geht folgenderma\ss{}en vor.
\begin{verbatim}
  SLS <- ()
  for i := 1 to n do
      EPS.insert(s[i].start)
      EPS.insert(s[i].end)
  while !EPS.empty() do
      q <- EPS.deleteMin()
      HandleEvent(q)

HandleEvent(q)
    if q is the startpoint of a line segment s[i] then
        SLS.insert(s[i])
        s' <- SLS.pred(s[i])
        s'' <= SLS.succ(s[i])
        if s[i] intersects s' or s'' to the right of q then
            compute the intersection point(s) and insert it/them into EPS
    if q is the endpoint of a line segment s[i] then
        s' <- SLS.pred(s[i])
        s'' <= SLS.succ(s[i])
        SLS.delete(s[i])
        if s' and s'' intersect to the right of q then
            compute the intersection point and insert it into EPS
    if q is the intersection of s' and s'' then
        output q
        switch s' and s'' in EPS
        if any of s' or s'' intersect any of its new neighbors to the right of q
          then
            compute the intersection point(s) and insert it/them into EPS
\end{verbatim}

\section{Triangulierung eines Polygons}

Die Eingabe ist ein einfaches 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$ in $y$-monotone Polygone zerlegen.

Wir l\"osen das Problem mit einem Sweepline-Algorithmus.
Der Event-Point-Schedule \texttt{EPS} enth\"alt die Ecken 
von $P$, sortiert von oben nach unten. Er wird als Stack
realisiert.
  
Der Sweepline-Status besteht aus der Folge der Intervalle,
in denen die horizontale Sweepline das Polygon schneidet,
von links nach rechts sortiert. Er wird als geordnetes 
W\"orterbuch realisiert. Jedes Intervall $I$ speichert
eine linke und eine rechte Polygonkante, die Start- und 
die Endkante des Intervalls, $I.\texttt{start}$ und 
$I.\texttt{end}$. Au\ss{}erdem speichert $I$ einen 
\emph{Helfer} $I.\texttt{helper}$. Dies ist die niedrigste 
Ecke des Polygons in dem geschlossenen Viereck definiert 
durch die Sweepline, $I.\texttt{start}$ und $I.\texttt{end}$. 
(bez\"uglich einer allgemeinen Sweepline, welche keine
Ecke des Polygons schneidet, aber $I$ als Intervall 
enth\"alt).  Beachte: $I.\texttt{helper}$ ist entweder ein 
Endpunkt von $I.\texttt{start}$ oder $I.\texttt{end}$, oder
eine Verschmelzungsecke.
  
\begin{verbatim}
  while !EPS.isEmpty() do
      q <- EPS.pop()
      handleVertex(q)

  // q ist Startecke: die zu q inzidenten Kanten liegen unter q, der 
  //                  Innenwinkel bei q ist < 180 Grad
  handleStartVertex(q)
      Erzeuge ein neues Intervall I mit den zu q inzidenten Kanten als
          Start- und  Endkante, und mit I.helper = q
      Fuege I in SLS ein

  // q ist regulaere Ecke: eine zu q inzidente Kante liegt ueber q
  //                       eine zu q inzidente Kante liegt unter q 
  handleRegularVertex(q) 
      I <- Intervall, das q enthaelt
      if I.helper ist Verschmelzungsecke then
          Fuege Diagonale von q zu I.helper ein
      aktualisiere I.start bzw. I.end
      I.helper <- q
  
  // q ist Trennungsecke: die zu q inzidenten Kanten liegen unter q,
  //                      der Innenwinkel bei q ist > 180 Grad 
  handleSplitVertex(q)
      I <- Intervall, das q enthaelt
      Fuege Diagonale von q zu I.helper ein
      Teile I in zwei Intervalle I1 und I2
      I1.helper <- q; I2.helper <- q

  // q ist Verschmelzungsecke: die zu q inzidenten Kanten liegen ueber q,
  //                           der Innenwinkel bei q ist > 180 Grad 
   handleMergeVertex(q)
      I1, I2 <- benachbarte Intervalle, die q enthalten
      if I1.helper ist Verschmelzungsecke then
          Fuege Diagonale von q zu I1.helper ein
      if I2.helper ist Verschmelzungsecke then
          Fuege Diagonale von q zu I2.helper ein
      Verschmelze I1 und I2 zu einem Intervall I 
      I.helper <- q

  // q ist Endecke: die zu q inzidenten Kanten liegen ueber q,
  //                der Innenwinkel bei q ist < 180 Grad 
   handleEndVertex(q)
      I <- Intervall, das q enthaelt
      if I.helper ist Verschmelzungsecke then
          Fuege Diagonale von q zu I.helper ein
      Loesche I 
\end{verbatim}

Das Sortieren der Ecken nach $y$-Koordinate ben\"otigt $O(n \log n)$
Zeit. Danach gibt es $n$ Ereignispunkte. Jeder Ereignispunkte kann in
$O(\log n)$ Zeit bearbeitet werden, da man nur konstant viele 
W\"orterbuchoperationen ausf\"uhren muss. Die Gesamtlaufzeit ist 
$O(n \log n)$.
 
Die Korrektheit des Algorithmus folgt, weil jede Trennungs- und 
Verschmelzungsecke durch eine Diagonale nach oben bzw. unten 
zerst\"ort wird. Die Definition der Helfer stellt sicher, dass 
die eingef\"ugten Diagonalen im Inneren des Polygons
liegen und sich nicht echt schneiden. Die Korrektheit der 
Helfer im Algorithmus folgt durch Induktion nach der Anzahl 
der Durchl\"aufe der \texttt{while}-Schleife und
durch Inspektion der einzelnen F\"alle.

\end{document}