Computational Geometry 24/25 - Material Page

Institute of Operating Systems and Computer Networks
- News
- - Courses
  - Theses
  - Projects
  - Publications
  - Software
  - Datasets
- - Team
  - Teaching
  - Theses & Jobs
  - Research
  - Publications
- - Courses
  - Theses
  - Projects
  - Publications
- Microprocessor Lab
- Spin-Offs
  - Docoloc
  - bliq (formerly AIPARK)
  - Confidential Technologies
- - IST.hub

Material

Lecture

We provide video recordings of the lecture from 2021 below. These alone cannot replace attendance in the ongoing semester: The course structure may differ.

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)
Tour Problems	[PDF] [Video]	Hamiltonian Cycles in Grid Graphs, MaxTSP (Russian), MaxTSP, Lawn Mowing and Milling, Min Stars Max Matching, Solving Hard to Approximate Easy, Geometric Max TSP, Longest Geometric Tours, Non-Simple Polygons with Min Perimeter, Cycle Cover with Turn Cost

Tutorial

Topic	Tutorial Material	References
Organisation and Convex Hulls	[PDF]	Big O Notation (DE, IBR), Big O Notation (EN, MIT OpenCourseWare)
Jordan Curves and Convex Hulls	[PDF]	Jordan Polygon Theorem, Winding Number
Farthest pairs	[PDF]	Dissertation of Michael Shamos
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
The Art Gallery Problem	[PDF]
Algorithm design and plane partitions	[PDF]