Algorithmische Geometrie

Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nchsten Nachbarn? Wie findet man schnell alle Stdte in einem rechteckigen Kartenausschnitt? Wie misst man die hnlichkeit von zwei Kurven?Mit solchen Fragen beschftigt sich die Algorithmische Geometrie. Dieses Buch gibt eine Einfhrung in algorithmische Techniken wie Sweep, Divide-and-Conquer, randomisierte inkrementelle Konstruktion, Dynamisierung, amortisierte Kostenanalyse und kompetitive Analyse. Es stellt wichtige geometrische Strukturen, wie konvexe Hlle, Voronoi-Diagramm und Delaunay-Triangulation sowie effiziente Datenstrukturen vor. Diese dritte Auflage wurde grndlich berarbeitet und erweitert. Sie bietet Dozent*innen die Mglichkeit, fr Vorlesungen und Seminare eine individuelle Stoffauswahl zu treffen, auch zu weiterfhrenden Themen wie zum Beispiel ausgewogene hherdimensionale Suchbume, schnelle Triangulierung, Vapnik-Chervonenkis Dimension, hnlichkeitsberechnung von Kurven, Bewegungsplanung und Inzidenzen geometrischer Objekte.