Computational Geometry 25/26 - Materialseite

Institut für Betriebssysteme und Rechnerverbund
- News
- Wir über uns
- Connected and Mobile Systems
- Verlässliche Systemsoftware
  - Übersicht
  - Team
  - Lehre
  - Arbeiten & Jobs
  - Forschung
  - Publikationen
- Algorithmik
- Mikroprozessorlabor
- Studium
- Service
- Spin-Offs
  - Docoloc
  - bliq (formerly AIPARK)
  - Confidential Technologies
- Forschungsverbünde
  - IST.hub

Material

Lecture

Hier werden Videoaufnahmen der Vorlesung von 2021 zur Verfügung gestellt. Diese allein können eine Teilnahme an der Vorlesung im laufenden Semester nicht ersetzen: Die Kursstruktur kann teils abweichen.

Topic	Lecture Material	References
Introduction	[PDF] [Video]
Convex Hull I	[PDF] [Video]	Jarvis' March, Quickhull
Convex Hull II	[PDF] [Video]	Preparata/Hong, Graham's Scan, Kirkpatrick/Seidel, Chan's algorithm
Closest Pairs of Points I	[PDF] [Video]	Shamos / Bentley, Ben-Or, Compute Median
Closest Pairs of Points II	[PDF] [Video]	Randomized Incremental Construction
Voronoi diagrams I	[PDF] [Video]
Voronoi diagrams II	[PDF] [Video]
Voronoi diagrams III	[PDF] [Video]	Fortune's Algorithm
Voronoi games	[PDF] [Video]	Ahn 2001, Ahn 2004, One-Round Voronoi Game, Cheong 2007, Muller / Preparata, Teramoto 2011, Voronoi Game on Graphs, One-Round Manhattan Voronoi Game
Polygon Triangulation	[PDF] [Video]	Robot Triangulation, Chazelle 1991, Clarkson 1989, Garey 1978, Kirkpatrick 1992, Tarjan 1988
Point Triangulation	[PDF] [Video]	Delaunay, Triangulations - ETH, MaxMin Angle, MinMax Angle, Mulzer-Rote MWT, Haas MWT, MaxMin Edge Length, MinMax Edge Length
Location Problems	[PDF] [Video]	Continuous Weber Problem, Continuous Fermat Weber Problem, Solving Hard to Approximate Easy, Median, Algebraic Degree of Geometric Optimization, Paths Among Obstacles, Impossibility of Solving Fifth Degree Equation (French)

Tutorial

Topic	Tutorial Material	References
Organisation and Convex Hulls	[PDF]	Big O Notation (DE, IBR), Big O Notation (EN, MIT OpenCourseWare)
Farthest pairs	[PDF]	Dissertation of Michael Shamos
Jordan Curves and Convex Hulls	[PDF]	Jordan Polygon Theorem, Winding Number
Voronoi diagrams and Enclosing disks	[PDF]	Optimal deterministic algorithms for 2d and 3d shallow cuttings, An optimal algorithm for higher-order Voronoi diagrams in the plane: The usefulness of nondeterminism, Farthest-polygon Voronoi diagrams
Convex hull of simple polygons and Algorithm design	[PDF]	On-line Construction of the Convex Hull of a Simple Polyline
The Art Gallery Problem	[PDF]	A linear algorithm for computing the visibility polygon from a point