Aktion	Zweigstelle	Standorte	Status	Frist	Vorbestellungen
Vorbestellen	Zweigstelle: 07., Urban-Loritz-Pl. 2a	Standorte: NN.MG Klein / College 6x - Magazin: bitte wenden Sie sich an die Infotheke	Status: Verfügbar	Frist:	Vorbestellungen: 0

Wie bestimmt man in einer Menge von Punkten am schnellsten zu jedem Punkt seinen nächsten Nachbarn? Wie lässt sich der Durchschnitt von zwei Polygonen berechnen? Wie findet man ein Ziel in unbekannter Umgebung?Mit solchen und ähnlichen Fragen beschäftigt sich die Algorithmische Geometrie, ein Teilgebiet der Informatik, dessen Entwicklung etwa 1975 begann und seitdem einen stürmischen Verlauf genommen hat.Dieses Lehrbuch gibt eine Einführung in häufig verwendete algorithmische Techniken wie Sweep, Divide-and-Conquer, randomisierte inkrementelle Konstruktion, Dynamisierung, amortisierte Kostenanalyse und kompetitive Analyse. Es stellt wichtige geometrische Strukturen vor wie konvexe Hülle, Voronoi-Diagramm und Delaunay-Triangulation sowie höherdimensionale Datenstrukturen.

 

 

/ AUS DEM INHALT: / / / 1 Grundlagen 1 1.1 Einführung 1 1.2 Ein paar Grundbegriffe 7 1.2.1 Topologie 7 1.2.2 Graphentheorie 11 1.2.3 Geometrie 18 1.2.4 Komplexität von Algorithmen 27 1.2.5 Untere Schranken 33 Lösungen der Übungsaufgaben 43 2 Das Sweep-Verfahren 51 2.1 Einführung 51 2.2 Sweep im Eindimensionalen 52 2.2.1 Das Maximum einer Menge von Objekten 52 2.2.2 Das dichteste Paar einer Menge von Zahlen 52 2.2.3 Die maximale Teilsumme 54 2.3 Sweep in der Ebene 57 2.3.1 Das dichteste Punktepaar in der Ebene 57 2.3.2 Schnittpunkte von Liniensegmenten 64 2.3.3 Die untere Kontur - das Minimum von Funktionen 78 2.3.4 Der Durchschnitt von zwei Polygonen 88 2.4 Sweep im Raum 92 2.4.1 Das dichteste Punktepaar im Raum 92 Lösungen der Übungsaufgaben 95 3 Geometrische Datenstrukturen 103 3.1 Einführung 103 3.2 Dynamisierung 106 3.2.1 Amortisiertes Einfügen: die Binärstruktur 109 3.2.2 Amortisiertes Entfernen durch gelegentlichen Neubau 115 3.2.3 Amortisiertes Einfügen und Entfernen 117 3.2.4 Einfügen mit gutem Verhalten im worst case 120 3.2.5 Entfernen mit gutem Verhalten im worst case 125 3.2.6 Einfügen und Entfernen mit gutem worst case 127 3.3 Interne Datenstrukturen für Punkte 130 3.3.1 Der fc-d-Baum 130 3.3.2 Der Bereichsbaum 139 3.3.3 Der Prioritätssuchbaum 144 Lösungen der Übungsaufgaben 151 4 Durchschnitte und Sichtbarkeit 159 4.1 Die konvexe Hülle ebener Punktmengen 159 4.1.1 Präzisierung des Problems und untere Schranke 160 4.1.2 Inkrementelle Verfahren 163 4.1.3 Ein einfaches optimales Verfahren 171 4.1.4 Der Durchschnitt von Halbebenen 174 4.2 Triangulieren eines einfachen Polygons 179 4.3 Konstruktion des Sichtbarkeitspolygons 185 4.3.1 Der Algorithmus 186 4.3.2 Verschiedene Sichten im Inneren eines Polygons 192 4.3.3 Das Kunstgalerie-Problem 194 4.4 Der Kern eines einfachen Polygons 197 4.4.1 Die Struktur des Problems 198 4.4.2 Ein optimaler Algorithmus 204 Lösungen der Übungsaufgaben 207 5 Distanzprobleme 211 5.1 Einführung 211 5.2 Definition und Struktur des Voronoi-Diagramms 213 5.3 Anwendungen des Voronoi-Diagramms 221 5.3.1 Das Problem des nächsten Postamts 221 5.3.2 Die Bestimmung aller nächsten Nachbarn 223 5.3.3 Der minimale Spannbaum 225 5.3.4 Der größte leere Kreis 228 5.4 Die Delaunay-Triangulation 233 5.4.1 Definition und elementare Eigenschaften 233 5.4.2 Die Maximalität der kleinsten Winkel 235 5.5 Verallgemeinerungen 239 5.5.1 Allgemeinere Abstandsbegriffe 239 5.5.2 Voronoi-Diagramme von Liniensegmenten 250 5.5.3 Anwendung: Bewegungsplanung für Roboter 255 Lösungen der Übungsaufgaben 261 6 Berechnung des Voronoi-Diagramms 269 6.1 Die untere Schranke 269 6.2 Inkrementelle Konstruktion 271 6.2.1 Aktualisierung der Delaunay-Triangulation 272 6.2.2 Lokalisierung mit dem Delaunay-DAG 277 6.2.3 Randomisierung 282 6.3 Sweep 286 6.3.1 Die Wellenfront 287 6.3.2 Entwicklung der Wellenfront 290 6.3.3 Der Sweep-Algorithmus für V(S) 291 6.4 Divide and Conquer 295 6.4.1 Mischen von zwei Voronoi-Diagrammen 296 6.4.2 Konstruktion von B(L, R) 298 6.4.3 Das Verfahren divide and conquer für V(S) 303 6.5 Geometrische Transformation 305 6.6 Verallgemeinerungen 307 Lösungen der Übungsaufgaben 309 7 Bewegungsplanung bei unvollständiger Information 313 7.1 Ausweg aus einem Labyrinth 316 7.2 Finden eines Zielpunkts in unbekannter Umgebung 324 7.3 Kompetitive Strategien 330 7.3.1 Suche nach einer Tür in einer Wand 333 7.3.2 Exponentielle Vergrößerung der Suchtiefe: ein Paradigma . . . 341 7.4 Suche nach dem Kern eines Polygons 350 7.4.1 Die Strategie CAB 351 7.4.2 Eine Eigenschaft der von CAB erzeugten Wege 357 Lösungen der Übungsaufgaben 365 Literatur 371 Index 379