Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


Literatur für Geometrische Algorithmen



Ein großer Teil des im vorliegenden Abschnitt dargelegten Materials ist erst vor relativ kurzer Zeit ausgearbeitet worden. Viele der von uns betrachteten Probleme und Lösungen wurden 1975 von M. Shamos vorgestellt. Eine große Anzahl geometrischer Algorithmen wurde in der Dissertation von Shamos behandelt; diese diente als Anregung für viele der in letzter Zeit durchgeführten Forschungsarbeiten und letzten Endes als Grundlage für die entscheidende Referenz auf diesem Gebiet, das Buch von Preparata und Shamos. Das Gebiet ist in rascher Entwicklung begriffen; im Buch von Edelsbrunner werden viele Forschungsergebnisse jüngeren Datums dargelegt.

Im wesentlichen gilt, daß jeder der von uns erörterten geometrischen Algorithmen in der entsprechenden Originalliteratur beschrieben ist. Die in Kapitel 25 behandelten Algorithmen zur Bestimmung der konvexen Hülle sind in den Arbeiten von Jarvis, Graham sowie Golin und Sedgewick zu finden. Die Verfahren für die Bereichssuche aus Kapitel 26 stammen aus dem Übersichtsartikel von Bentley und Friedman, der zahlreiche Hinweise auf Originalquellen enthält (von besonderem Interesse ist der Originalartikel von Bentley selbst über kD-Bäume, den er als Student des letzten Studienjahres verfaßte). Die Darlegung der Probleme des nächsten Punktes in Kapitel 28 beruht auf der Arbeit von Shamos und Hoey aus dem Jahre 1976, und die Schnittalgorithmen aus Kapitel 27 stammen aus ihrer Arbeit von 1975 sowie aus dem Artikel von Bentley und Ottmann.

Die beste Verfahrensweise für jemanden, der mehr über geometrische Algorithmen erfahren möchte, besteht jedoch darin, einige von ihnen zu implementieren, um ihre Eigenschaften und die Eigenschaften der Objekte, mit denen sie operieren, kennenzulernen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]