Kapitel 1 – Einführung & Grundlagen

Folien: 📄 01-basics.pdf

Was ist Computational Geometry?

Computational Geometry (algorithmische Geometrie) befasst sich mit Entwurf und Analyse von Algorithmen und Datenstrukturen für geometrische Probleme. Die Probleme kommen u.a. aus:

• Computergrafik
• Visualisierung
• Geoinformationssystemen (GIS)
• Computer Vision und Mustererkennung
• Robotik

Als eigenständige Disziplin hat sich das Gebiet zwischen 1975 und 1980 etabliert. Ein Meilenstein ist die Dissertation von Michael Shamos (1978), aus der später das Buch von Preparata/Shamos wurde.

Der Fokus liegt dabei weniger darauf, dass man ein geometrisches Problem lösen kann (naiv geht fast alles), sondern darauf, es effizient zu lösen. Und das heißt: mit nachweisbarer, möglichst optimaler asymptotischer Laufzeit. Deshalb gehören zu den Grundlagen auch das Berechnungsmodell und das O-Kalkül.

Aufbau des Kapitels

Abschnitt	Inhalt
1.1 Typische Probleme	Fünf Motivationsbeispiele, die jeweils zu einem späteren Kapitel führen
1.2.1 Geometrische Objekte	Punkte, Vektoren, affine Räume, Strecken, Geraden, Polygone
1.2.2–1.2.3 Primitive Operationen & Rechenmodell	Was „konstante Zeit“ heißt, Orientierungstest, Real RAM
1.2.4–1.2.5 Laufzeit & O-Kalkül	Laufzeitfunktionen, $O,\Omega,\Theta,o,\omega$
1.2.6 Master-Theorem	Laufzeit von Divide-and-Conquer-Rekursionen

Abschnitt 1.2.7, das Beispiel 2D-Hülle, wird in Kapitel 2 ausführlich behandelt.