|
Folien
Übungen
Bilder
 Zurück
|
Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 7: Geometrische Algorithmen
|
|
|
Die
Geometrie ist eines der ältesten Gebiete der Mathematik, dessen Wurzeln
bis in die Antike zurückreichen. Algorithmische Aspekte und die Lösung
geometrischer Probleme mit Hilfe von Computern haben aber erst in jüngster
Zeit verstärktes Interesse gefunden. Der Grund dafür liegt sicherlich in
gewandelten Anforderungen durch neue Anwendungen, die von der
Bildverarbeitung, Computer-Graphik, Geographie, Kartographie usw. bis hin
zum physischen Entwurf höchstintegrierter Schaltkreise reichen.
So ist in den letzten Jahren ein neues Forschungsgebiet entstanden, das
unter dem Namen ``Algorithmische Geometrie'' (Computational Geometry)
inzwischen einen festen Platz innerhalb des Gebiets ``Algorithmen und
Datenstrukturen'' einnimmt.
Wir werden uns in diesem Kapitel auf die Darstellung einiger weniger,
aber durchaus grundlegender Probleme, Datenstrukturen und Algorithmen
beschränken. Im ersten Abschnitt stellen wir das Scan-line-Prinzip vor,
das sich als Mittel zur Lösung zahlreicher geometrischer Probleme
inzwischen bewährt hat. Wie das Divide-and-conquer-Prinzip zur Lösung
geometrischer Probleme eingesetzt werden kann, zeigt der Abschnitt über Divide-and-conquer-Prinzip.
Zur Speicherung und Manipulation von Daten mit einer räumlichen
Komponente reichen die bekannten, zur Speicherung von Mengen ganzzahliger
Schlüssel geeigneten Strukturen nicht aus. In Abschnitt Geometrische Datenstrukturen
stellen wir einige Strukturen vor, die dafür in Frage kommen, und zwar
Segment-, Intervall-, Bereichs- und
Prioritäts-Suchbäume.
Die Folien orientieren sich an der Vorlesung Geometrische Algorithmen.
|
|
Bei Fragen zu
dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.
|
|