Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen

Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nachsten Nachbarn? Wie lasst sich der Durchschnitt von zwei Polygonen berechnen? Wie findet man ein Ziel in unbekannter Umgebung? Mit solchen Fragen beschaftigt sich die Algorithmische Geometrie.

Dieses Buch gibt eine Einfuhrung in algorithmische Techniken wie Sweep, Divide-and-Conquer, randomisierte inkrementelle Konstruktion, Dynamisierung, amortisierte Kostenanalyse und kompetitive Analyse. Es stellt wichtige geometrische Strukturen vor wie konvexe Hulle, Voronoi-Diagramm und Delaunay-Triangulation sowie hoeherdimensionale Datenstrukturen.

Diese zweite Auflage wurde grundlich uberarbeitet, sie enthalt uber 60 Aufgaben mit Loesungen.