1.2.2 Primitive Operationen & 1.2.3 Rechenmodell

Um Laufzeiten geometrischer Algorithmen sauber angeben zu können, muss man festlegen, was ein Rechenschritt ist. Dazu dienen die primitiven Operationen und das Rechenmodell.

1.2.2 Primitive geometrische Operationen

Primitive Operationen sind Operationen, die nur Objekte konstanter Größe betreffen. Sie gelten im Rechenmodell als Operationen mit konstanter Laufzeit und konstantem Speicherbedarf, also $O(1)$.

Primitiv ✔	Nicht primitiv ✘
Schnittpunkt zweier Geraden	Liegt ein Punkt in einem Polygon?
Liegt ein Punkt im Halbraum einer Hyperebene?	Schnitt zweier Polygone
Links-/Rechtstest Punkt vs. gerichtete Gerade	Konvexe Hülle von $n$ Punkten
Abstand zweier Punkte

Warum ist „Punkt in Polygon“ nicht primitiv? Ein Polygon hat $n$ Ecken, $n$ ist nicht konstant. Der Test muss (im Allgemeinen) alle $n$ Kanten anschauen und kostet $O(n)$.

Merkregel: Primitiv ist, was sich mit einer festen Anzahl arithmetischer Operationen auf einer festen Anzahl von Koordinaten berechnen lässt, unabhängig von der Eingabegröße.

Der Orientierungstest

Steht so nicht explizit auf den Folien von 1.2.2, ist aber das Beispiel „Punkt liegt im Halbraum einer Hyperebene“ in 2D. In Kapitel 2 („liegt $r$ links von $pq$?“, „Rechtskurve?“) wird er ständig benutzt.

Gegeben drei Punkte $a,b,c\in\mathbb{R}^2$. Liegt $c$ links, rechts oder auf der gerichteten Geraden durch $a$ nach $b$?

Man bildet das 2D-Kreuzprodukt der Vektoren $b-a$ und $c-a$:

$$\operatorname{orient}(a,b,c) := (b_x-a_x)(c_y-a_y) - (b_y-a_y)(c_x-a_x) = \det\begin{pmatrix} 1 & a_x & a_y\\ 1 & b_x & b_y\\ 1 & c_x & c_y\end{pmatrix}$$

Ergebnis	Lage von $c$	Kurve $a\to b\to c$
$>0$	links von $\vec{ab}$	Linkskurve (gegen den Uhrzeigersinn)
$<0$	rechts von $\vec{ab}$	Rechtskurve (im Uhrzeigersinn)
$=0$	auf der Geraden $ab$	keine Kurve, kollinear

Warum funktioniert das? $b-a$ ist die Richtung, in die man läuft, $c-a$ zeigt zum Testpunkt. Das Kreuzprodukt ist positiv, wenn man $b-a$ gegen den Uhrzeigersinn um weniger als 180° drehen muss, um auf $c-a$ zu kommen, wenn also $c$ links liegt.

Zum Ausprobieren: Zieh die Punkte. Die grüne Seite ist „links von $\vec{ab}$“, die orange „rechts“. Lege $c$ genau auf die Gerade, dann wird das Ergebnis 0.

orient(a,b,c) = (b_x−a_x)(c_y−a_y) − (b_y−a_y)(c_x−a_x) = (8)·(5) − (3)·(3) = 31
c liegt links von a→b – Linkskurve (gegen den Uhrzeigersinn). Fläche des Dreiecks abc = |31| / 2 = 15.5. · Ziehe a, b oder c (Punkte rasten auf dem Gitter ein).

Zusatzbedeutung: $\tfrac12\lvert\operatorname{orient}(a,b,c)\rvert$ ist der Flächeninhalt des Dreiecks $abc$. Ist er 0, ist das Dreieck entartet, die Punkte sind kollinear.

Beispiele:

$a$	$b$	$c$	Rechnung	Ergebnis
$(0,0)$	$(2,0)$	$(1,1)$	$2\cdot1 - 0\cdot1 = 2$	links ✔ (über der x-Achse)
$(0,0)$	$(2,0)$	$(1,-1)$	$2\cdot(-1) - 0\cdot1 = -2$	rechts
$(0,0)$	$(2,0)$	$(5,0)$	$2\cdot0 - 0\cdot5 = 0$	kollinear
$(0,0)$	$(1,2)$	$(2,1)$	$1\cdot1 - 2\cdot2 = -3$	rechts

Kosten: 2 Multiplikationen, 5 Subtraktionen, ein Vorzeichenvergleich, also primitiv, $O(1)$.

Warum Kreuzprodukt statt Winkel?

Man könnte auch Winkel mit atan2 berechnen und vergleichen. Der Orientierungstest liefert dieselbe Information aber ohne trigonometrische Funktionen, ohne Division und ohne Sonderfall bei senkrechten Geraden (keine Steigung $\infty$). Er ist schneller und weniger anfällig für Rundungsfehler.

1.2.3 Rechenmodell: Real RAM

Um Laufzeiten zu zählen, braucht man ein abstraktes Maschinenmodell. In der algorithmischen Geometrie ist das die Real RAM (Real Random Access Machine):

• Abzählbar unendlich viele Speicherzellen, adressierbar durch natürliche Zahlen.
• Jede Speicherzelle kann beliebige reelle Zahlen oder ganze Zahlen enthalten, mit unendlicher Genauigkeit.
• Folgende Operationen sind primitiv und kosten konstante Zeit:
  • arithmetische Operationen: $+,\ -,\ \times,\ /,\ \bmod,\ \operatorname{div}$
  • Vergleiche reeller Zahlen
  • indirekte Adressierung (Zeiger, Arrayzugriff)
  • Wurzeln, trigonometrische Funktionen, Logarithmen

Real RAM vs. echter Computer (Ergänzung)

Das Modell ist eine Idealisierung:

Real RAM	Echter Rechner (double)
exakte reelle Zahlen	64-Bit-Gleitkomma, ca. 16 Dezimalstellen
$\operatorname{orient}=0$ ist exakt entscheidbar	Rundungsfehler, fast kollineare Punkte bekommen evtl. das falsche Vorzeichen
$\sqrt{\ }$, $\sin$ kosten $O(1)$	kosten real deutlich mehr als $+$ und $\times$

Für die Laufzeitanalyse ist das Modell richtig. Für die Implementierung muss man wissen, dass Tests auf „$=0$“ mit Gleitkommazahlen fragil sind. Die Folien zu Kapitel 2 sagen beim naiven Algorithmus ausdrücklich: „Rundungsfehler der Gleitkommaarithmetik vernachlässigen“. Abhilfen in der Praxis sind ganzzahlige Koordinaten, exakte Arithmetik oder robuste Prädikate.