| 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)
|
Lectures - Lecture #1, Nov 01, 2022 (Introduction)
- Lecture #2, Nov 08, 2022 (Convex hull)
- Lecture #3, Nov 15, 2022 (Convex hull)
- Lecture #4, Nov 22, 2021 (Closest pair of points)
- Lecture #5, Nov 29, 2022 (Closest pair of points)
- Lecture #6, Dec 06, 2022 (Voronoi diagram)
- Lecture #7, Dec 12, 2022 (Voronoi diagram)
- Lecture #8, Dec 19, 2022 (Voronoi diagram)
- Lecture #9, Jan 10, 2023 (Voronoi games)
- Lecture #10, Jan 17, 2022 (Polygon triangulation)
- Lecture #11, Jan 24, 2022 (Point triangulation)
- Lecture #12, Jan 31, 2022 (Location problems)
- Lecture #13, Feb 07, 2023
Exercise / discussion meetings - Meeting #1, Nov 10, 2022 // Slides, Euler characteristic, Four color theorem
- Meeting #3, Dec 08, 2022 // Slides, Rotating calipers
- Exercise Sheet #1, Dec 08, 2022, due on Jan 12, 2023 // Download
- Meeting #4, Dec 15, 2022 // Slides, Farthest-point Voronoi diagram & Smallest enclosing circle, Fold and Cut, Abstract Voronoi diagrams - Rolf Klein
- Meeting #5, Jan 12, 2023 // Trapezoidal maps - Seidel
- Exercise Sheet #2, Jan 12, 2023, due on Jan 26, 2023 // Download
- Meeting #6, Jan 26, 2023 // Slides, How to guard a museum
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 Michael. |
