Obwohl einfache Schnittprobleme, z.B. zwischen Geraden in der Ebene, vom mathematischen Standpunkt aus nicht interessant sind, treten jedoch beim Schnitt von tausenden von Geraden Effizienzprobleme auf, zu deren Behandlung spezielle Algorithmen erforderlich sind. Die Entwicklung und theoretische Analyse effizienter Algorithmen für solche Probleme mit großen Datenmengen geometisch einfacher Objekte ist der Gegenstand der algorithmischen Geometrie. Das theoretische interesse an solchen Fragestellungen wird durch viele praktische Anwendungen in der Computergrafik, im Computer Aided Design, im VLSI Design, in der Robotik, usw. gestützt.
Im ersten Teil der Vorlesung sollen zwei grundlegende Paradigmen der algorithmischen Geometrie, das Sweepline-Paradigma und das Divide- and Conquer-Paradigma anhand exemplarischer Fälle besprochen werden.
Der zweite Teil beschäftigt sich mit effizienten Algorithmen zum Berechnen von konvexen Hüllen und Voronoi-Diagrammen. Dabei werden auch konkrete Anwendungen aus dem Bereich der Computergrafik, des Computer Aided Design und der Robotik diskutiert.
