Geometrische Algorithmen sind eine Kategorie von Berechnungsmethoden, die zur Lösung von Problemen im Zusammenhang mit geometrischen Formen und deren Eigenschaften verwendet werden. Diese Algorithmen befassen sich mit Objekten wie Punkten, Linien, Polygonen und anderen geometrischen Figuren.
In vielen Bereichen der Informatik, wie z.B. Robotik, Computergrafik, virtuelle Realität und geografische Informationssysteme, ist es notwendig, räumliche Daten zu speichern, zu analysieren und zu erstellen oder zu manipulieren. Dieser Kurs befasst sich mit den algorithmischen Aspekten dieser Aufgaben: Wir untersuchen Techniken und Konzepte, die für den Entwurf und die Analyse geometrischer Algorithmen und Datenstrukturen erforderlich sind. Jede Technik und jedes Konzept wird anhand eines Problems aus einem der oben genannten Anwendungsbereiche veranschaulicht. Ziele: Am Ende dieses Kurses sollten die Teilnehmer in der Lage sein, - zu entscheiden, welcher Algorithmus oder welche Datenstruktur zu verwenden ist, um ein gegebenes geometrisches Grundproblem zu lösen, - neue Probleme zu analysieren und mit Hilfe der Konzepte und Techniken aus dem Kurs eigene effiziente Lösungen zu finden. Voraussetzungen: Um diesen Kurs erfolgreich zu absolvieren, sollten Sie bereits über Grundkenntnisse in Algorithmen und Mathematik verfügen. Hier eine kurze Liste dessen, was Sie wissen sollten: - O-Notation, Ω-Notation, Θ-Notation; wie man Algorithmen analysiert - Grundrechenarten: Manipulation von Summen, Lösen von Rekursen, Arbeiten mit Logarithmen usw. - Grundlegende Wahrscheinlichkeitstheorie: Ereignisse, Wahrscheinlichkeitsverteilungen, Zufallsvariablen, Erwartungswerte usw. - Grundlegende Datenstrukturen: verknüpfte Listen, binäre Suchbäume usw. - Graphenterminologie - Programmierkenntnisse für praktische Aufgaben Der Großteil des Materials in diesem Kurs basiert auf dem folgenden Buch: M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithmen und Anwendungen (3. Auflage). Springer-Verlag, 2008. Es ist nicht zwingend erforderlich, dieses Buch zu kaufen. Wenn Sie jedoch mehr wissen möchten, als in diesem Kurs angeboten wird, oder einen weiteren Blick auf das in den Vorlesungen besprochene Material werfen möchten, empfehlen wir den Kauf dieses Buches. Die Videovorlesungen enthalten ein paar sehr kleine Fehler. Eine Liste dieser Fehler finden Sie unter Ressourcen. Wenn Sie glauben, einen Fehler gefunden zu haben, melden Sie das Problem, indem Sie auf die quadratische Flagge am Ende der Vorlesung oder des Quiz klicken, in der Sie den Fehler gefunden haben.
