| Content | Geometric algorithms are of fundamental interest for a large spectrum of topics, both from theory and practice. In this class, we will start from the basic foundations, and work our way towards advanced topics.
In this semester, we will try a special online format, with participant from different countries, giving us the opportunity to do international exchange in the same classroom. We will discuss how to make the best of this opportunity - so feel free to bring in new ideas and suggestions. Topics are: - Geometric problems and data structures
- Convex hulls
- Closest pairs
- Voronoi diagrams
- Polygon triangulation
- Point triangulation
- Location problems
- Tours and polygons
|
| References | - Mark de Berg, Marc van Kreveld, Mark Overmars and Otfried Schwarzkopf: Computational Geometry: Algorithms and Applications, Second. Edition, pages 367, Springer-Verlag, 2000 (deBerg2000, BibTeX)
- Rolf Klein: Algorithmische Geometrie, pages 1-355, examen.press, 1997 (Klein1997, BibTeX)
- Franco P. Preparata and Michael Ian Shamos: Computational Geometry: An Introduction, Springer, 1985 (Preparata1985, BibTeX)
|
General announcements - The next lecture will be streamed on February 15 on YouTube.
- The next exercise / discussion meeting will be on February 16.
Lectures - Lecture #1, Nov 02, 2021 (Introduction)
- Lecture #2, Nov 09, 2021 (Convex hull)
- Lecture #3, Nov 16, 2021 (Convex hull)
- Lecture #4, Nov 23, 2021 (Closest pair of points)
- Lecture #5, Nov 30, 2021 (Closest pair of points)
- Lecture #6, Dec 07, 2021 (Voronoi diagram)
- Lecture #7, Dec 14, 2021 (Voronoi diagram)
- Lecture #8, Dec 21, 2021 (Voronoi diagram)
- Lecture #9, Jan 11, 2022 (Voronoi games)
- Lecture #10, Jan 18, 2022 (Polygon triangulation)
- Lecture #11, Jan 25, 2022 (Point triangulation)
- Lecture #12, Feb 01, 2022 (Location problems)
- Lecture #13, Feb 15, 2022
- Video: [Youtube], [IBR]
- Slides: [pdf]
- Original publications: 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
Exercise / discussion meetings - Meeting #1, Nov 18, 2021 // Slides, Convex layers, Euler characteristic
- Meeting #2, Dec 08, 2021 // Slides, Wallace-Bolyai-Gerwien theorem, Visualizing scissors congruence, numberphile video on Hilbert's third problem, Rotating calipers
- Meeting #3, Jan 19, 2022 // Slides, Smallest enclosing disk - Welzl, Closest point problems - Shamos and Hoey, k-center problem, Smallest annuli with outliers, Abstract Voronoi diagrams - Rolf Klein
- Meeting #4, Feb 02, 2022 // Slides, Trapezoidal maps - Seidel, Triangulation hierarchy - Kirkpatrick, Order type realization, Irrational guards, AGP is exist-R complete
- Meeting #5, Feb 16, 2022 // Slides, k-dops collision detection, Intersection of convex polygons, Geometric intersection problem, Visibility polygon demo site
Mailing list There is a mailing list for this class. Please sign up, as we will use it for communication. This list is moderated; participants from outside of TU Braunschweig will be approved manually, which may cause a slight initial delay. If you run into any problems, please contact Christian. |
