\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} {Satz}
\newtheorem {problem}[theorem] {Problem}
\newtheorem {lemma}[theorem] {Lemma}
\newtheorem {observation}[theorem] {Observation}
\newtheorem {corollary}[theorem] {Corollary}
\newtheorem {claim}[theorem] {Claim}


\title{Bestimmung des engsten Punktpaares
}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\noindent
\textbf{Gegeben}: Eine Menge 
$P = \{p_1, p_2, \dots , p_n\}$ von Punkten in der Ebene, 
so dass die $x$-Koordinaten $p_i\texttt{.x}$ paarweise verschieden sind.


\noindent
\textbf{Gesucht}: Ein Paar $\{p_i, p_j\}$ mit $i \neq j$, so dass
der euklidische Abstand $d(p_i, p_j)$ minimal ist.


In der naiven L\"osung probiert man alle $\binom{n}{2}$ 
Paare von verschiedenen Punkten und w\"ahlt das Paar mit
minimalem Abstand. Dadurch erh\"alt man eine Laufzeit von $O(n^2)$.
Wir werden nun sehen, wie man diese Laufzeit durch
Divide and Conquer auf $O(n \log n)$ verringern kann.


Vorverarbeitung:
Lege zwei Listen an, \texttt{xList} und \texttt{yList}.
Diese Listen enthalten die Punkte aus $P$, sortiert nach
der $x$-Koordinate (\texttt{xList}) bzw.\@ nach der 
$y$-Koordinate (\texttt{yList}).
Die Vorverarbeitungszeit betr\"agt  $O(n \log n)$.
Der Pseudocode f\"ur den Algorithmus ist wie folgt:
\begin{verbatim}
  // Eingabe: xList: Punkte nach x-Koordinate sortiert
  //          yList: Punkte nach y-Koordinate sortiert
  // Ausgabe (d, p, q): d ist der Abstand des engsten Paares {p, q}
  CP(xList, yList)
    if xList.size < 4 then
      solve the problem brute force
      return 
    m <- median element of xList
    // Aufteilen der Listen
    xListL <- all points r in xList with r.x <= m.x
    xListR <- all points r in xList with r.x > m.x
    yListL <- all points r in yList with r.x <= m.x 
                (sorted according to the order of yList)
    yListR <- all points r in yList with r.x > m.x
                (sorted according to the order of yList)
    // Rekursiver Aufruf
    (dL, pL, qL) <- CP(xListL, yListL)
    (dR, pR, qR) <- CP(yListR, yListR)
    (d, p, q) <- (dL < dR) ? (dL, pL, qL) : (dR, pR, qR)
    // Finden eines potentiell engeren Paares
    yList' <- all points r in yList with |r.x - m.x| <= d 
                (sorted according to the order in yList) 
    for all points r in yList' in order
      determine all distances between r and the 9 succeeding elements in yList',
      take the minimum and change the global minimum (d, p, q) if necessary
    return (d, p, q)
\end{verbatim}

Die Zeit f\"ur das Aufteilen der Listen und f\"ur 
das Finden eines potentiell engeren Paares ist $O(n)$. 
Somit erh\"alt man eine Rekursionsgleichung der Form
  $T(n) = 2T(n/2) + O(n)$, so dass $T(n) = O(n \log n)$ ist.

Durch ein Volumenargument sieht man, dass es gen\"ugt, nur 
die Abst\"ude zu neun Nachfolgern eines Punktes $r$ in 
\texttt{yList'} zu bestimmen, um ein Paar zu finden,
dessen Abstand kleiner als \texttt{d} ist (wenn es existiert).
Die Laufzeit $O(n \log n)$ ist optimal in einem geeigneten 
Entscheidungsbaummodell.
\end{document}