1.1 Typische Probleme

Die Folien motivieren die Vorlesung mit fünf Alltagsproblemen. Jedes davon hat einen naiven, aber zu langsamen Lösungsansatz, und jedes führt zu einem eigenen Kapitel.

Kapitelverweise

Die Verweise auf den Folien („Chapter 2, 5, 6, 7“) stammen aus einer älteren Gliederung. Unten stehen die Kapitelnummern nach der aktuellen Inhaltsübersicht.

a) Kartenüberlagerung im GIS → Schnitt von Liniensegmenten (§3)

In einem Geoinformationssystem liegen Informationen in getrennten Kartenebenen vor (Straßen, Flüsse, Bahnlinien, Orte, Landnutzung …). Jede Karte ist eine Ebene.

Frage: Finde alle Brücken, d.h. alle Schnittpunkte von Straßen mit Flüssen.

Straßen und Flüsse sind als Polygonzüge gespeichert. Gesucht sind also alle Schnittpunkte zwischen den Segmenten zweier Polygonzug-Mengen.

Naiv: Jedes Straßensegment mit jedem Flusssegment schneiden. Bei $n$ Straßen- und $m$ Flusssegmenten sind das $n\cdot m$ Tests. Bei realen Karten mit Millionen Segmenten ist das nicht machbar, zumal es in der Regel nur wenige echte Schnitte gibt.

Ziel (§3): ein Algorithmus, dessen Laufzeit von der Zahl $n$ der Segmente und der Zahl $k$ der tatsächlichen Schnitte abhängt (Sweep-Line, $O((n+k)\log n)$).

Beispiel aus de Berg et al.: Städte, Flüsse und Bahnlinien Westkanadas und ihre Überlagerung.

b) Datenbankabfrage → Bereichsanfragen (§4)

Eine Firma speichert für jeden Mitarbeiter Name, Geburtsdatum und Monatsgehalt.

Frage: Finde alle Mitarbeiter, die zwischen 1995 und 2000 geboren sind und zwischen 4.000 € und 5.000 € verdienen.

Trick: Das Geburtsdatum wird in eine sortierbare Zahl umgerechnet:

$\text{Datum} \mapsto 10.000\cdot\text{Jahr} + 100\cdot\text{Monat} + \text{Tag}$

Beispiel: 18.08.1998 ↦ 19.980.818.

Damit ist jeder Mitarbeiter ein Punkt in der Ebene (x = Geburtsdatum, y = Gehalt). Die Abfrage fragt nach allen Punkten in einem achsenparallelen Rechteck $[19.950.000,\ 20.009.999]\times[4.000,\ 5.000]$. Das ist eine 2D-Bereichsanfrage (range query).

In der Praxis haben solche Anfragen oft sehr viele Dimensionen, eine pro Attribut.

c) Kartenabfrage → Punktlokalisierung (§6)

Frage: In welchem Land liegt eine gegebene geografische Position?

Für Menschen ist das auf einer Karte trivial, für den Computer nicht: Die Karte ist eine Zerlegung der Ebene in Polygone, und für einen Anfragepunkt muss das Polygon gefunden werden, das ihn enthält.

Wichtig ist die Geschwindigkeit: Solche Anfragen laufen in Echtzeit, z.B. in Navigationssystemen oder bei jedem Mausklick („auf welches Fenster bzw. grafische Objekt wurde geklickt?“). Man darf vorverarbeiten, aber jede einzelne Anfrage muss schnell sein (Ziel: $O(\log n)$).

d) Kunstgalerie → Polygon-Triangulierung (§7)

Eine Kunstgalerie soll mit drehbaren Überwachungskameras ausgestattet werden.

Frage: Wie viele Kameras braucht man mindestens, und wo platziert man sie?

Modellierung:

• Der Grundriss der Galerie ist ein einfaches Polygon.
• Kamerapositionen sind Punkte im Polygon. Eine Kamera sieht alles, was sie per Sichtlinie innerhalb des Polygons erreicht.
• Extremfall: Ein konvexes Polygon lässt sich von einer Kamera an beliebiger Stelle überwachen, denn jede Sichtlinie bleibt drin (siehe Konvexität).

Daraus folgt: Zerlegt man das Polygon in Dreiecke (Triangulierung), reicht eine Kamera pro Dreieck, denn Dreiecke sind konvex. Das ist eine obere Schranke für die Kamerazahl.

Besser geht es, wenn man Kameras geschickter platziert, z.B. auf bestimmten Diagonalen oder in bestimmten Ecken. Dann deckt eine Kamera mehrere Dreiecke ab. Das führt zum Art-Gallery-Theorem: $\lfloor n/3\rfloor$ Kameras reichen immer für ein Polygon mit $n$ Ecken. (Ergänzung, kommt in §7)

Bezug zur Grafik: GPUs verarbeiten nur Dreiecke. Jedes CAD-System muss deshalb beliebige Polygone automatisch triangulieren können.

e) Nächste Telefonzelle → Voronoi-Diagramme & Delaunay-Triangulierung (§5)

Man muss auf dem Campus dringend telefonieren, hat kein Handy, kennt aber ein paar Telefonzellen in der Nähe.

Frage: Welche Telefonzelle ist am nächsten?

Idee: Man zerlegt die Karte vorab in Regionen, sodass jede Region genau die Punkte enthält, für die eine bestimmte Telefonzelle die nächste ist. Dann ist die Frage eine Punktlokalisierung.

Weiterführende Fragen:

• Welche Form haben diese Regionen? (Antwort in §5: konvexe Polygone, nämlich Schnitte von Halbebenen)
• Wie berechnet man sie effizient?

Diese Zerlegung heißt Voronoi-Diagramm. Ihr Dual ist die Delaunay-Triangulierung, siehe Praktikumsaufgabe 4.

Zusammenfassung

Problem	Geometrische Formulierung	Kapitel
Brücken finden	Schnitte zweier Segmentmengen	§3
Mitarbeiter filtern	Punkte in achsenparallelem Rechteck	§4
Land zur Position	Polygon, das einen Punkt enthält	§6
Kameras platzieren	Triangulierung einfacher Polygone	§7
Nächste Telefonzelle	Voronoi-Diagramm	§5

Gemeinsam ist allen: Der naive Ansatz ist einfach, aber zu langsam. Die Kunst liegt in effizienten Algorithmen mit bewiesener Laufzeit.