Die Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Verwaltung des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Mathematik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Universität Bremen
Zeige Systems Engineering-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Informatik-Format Pdf_icon Digitale Medien-Format Pdf_icon

Informatik-Ansicht

Computational Geometry


Computational Geometry
Modulnummer
ME-699.10
Master
Pflicht/Wahl
Wahl Basis Ergänzung
Sonderfall
Zugeordnet zu Masterprofil
Basis Ergänzung
Sicherheit und Qualität
KI, Kognition, Robotik
Digitale Medien und Interaktion
Modulbereich : Mathematik und Theoretische Informatik
Modulteilbereich : 699 Spezielle Gebiete der Theoretischen Informatik
Anzahl der SWS
V UE K S Prak. Proj.
3 1 0 0 0 0 4
Kreditpunkte : 6 Turnus

i. d. R. angeboten alle 2 Semester

Formale Voraussetzungen : -
Inhaltliche Voraussetzungen : Einfaches mathematisches und algorithmisches Denken.
Vorgesehenes Semester : ab 1. Semester
Sprache : Deutsch/Englisch
Ziele :
  • Kenntnis und Beherrschung einiger wichtiger Algorithmen und Datenstrukturen in der algorithmischen Geometrie.
  • Kenntnis und Verständnis einiger typischer Arten der Beweisführung in der algorithmischen Geometrie, um die Korrektheit und die Komplexität der Algorithmen und Datenstrukturen zu zeigen.
  • Zahlreicher exemplarische Anwendungen dieser Algorithmen, insbesondere in der Computergraphik, aber auch in anderen Gebieten.
  • Tieferes Verständnis für die Gründe, warum diese dadurch sehr effizient werden.
Inhalte :
  • Quadtrees / Octrees, Texturkompression, Isosurfaces, Terrain-Visualisierung.
  • KD-trees, BSP-Trees, Boolesche Operationen auf Objekten, Textursynthese, Bounding-Volumen-Hierarchien.
  • Kinetische Datenstrukturen, Collision Detection.
  • Konvexe Hülle und deren Anwendungen.
  • Voronoi- und Delaunay-Diagramme, Plazierungsprobleme, Approximation des Traveling Salesman Problems.
  • Range-Tree und Priority-Search-Tree, Range Queries auf dem Gitter.

Bemerkung: die genaue Zusammenstellung der Themen wird jedesmal ein wenig variiert bzw. erweitert.

Die Vorlesung bewegt sich an der Schnittstelle zwischen algorithmischer Geometrie und Computer-Graphik. Daher werden keine praktischen, sondern nur (einfache) theoretische Übungsaufgaben gestellt werden.

Unterlagen (Skripte, Literatur, Programme usw.) :
  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars: Computational Geometry: Algorithms and Applications; Springer
  • Franco P. Preparata, Michael Ian Shamos: Computational Geometry: An Introduction; Springer (schon etwas älter, aber immer noch ein klassiker)
  • Rolf Klein: Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen; Springer
  • Joseph O’Rourke: Computational Geometry in C. Cambridge University Press
  • G. Zachmann & E. Langetepe: Geometric Data Structures for Computer Graphics, CRC Press, 2006, ISBN: 9781568812359 (ehemals AK Peters)
Form der Prüfung : i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Arbeitsaufwand
Präsenz 56
Übungsbetrieb/Prüfungsvorbereitung 124
Summe 180 h
Lehrende: Prof. Dr. G. Zachmann Verantwortlich Prof. Dr. G. Zachmann
Zurück

Zeige Systems Engineering-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Informatik-Format Pdf_icon Digitale Medien-Format Pdf_icon