| Semester | |
| Programmes | Master Informatik, Master Wirtschaftsinformatik |
| IBR Group | ALG (Prof. Fekete) |
| Type | Vorlesung/Übung |
| Lecturer | |
| Assistant | |
| Credits | 5 |
| Hours | 2+1+1 |
| Time & Place | Lectures: Tuesdays, 15:00 - 16:30 CET (10am EDT, 9am EST; 7:30pm IST), online
Plenary tutorial : Some Thursdays, 11:30 - 13:00 CET (*); online
Small tutorial: TBA
(*) May be subject to change, TBA
|
| Start | Lecture: Oct 27, 2020
Plenary Tutorial: TBA
Small Tutorial: TBA |
| Prerequisites | none |
| Language | English |
| Certificates | Studienleistung ("Study requirement"): TBA
Exam: Oral exam
|
| 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
- Delaunay triangulations
- Polygon triangulations
- Advanced research topics
|
| 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, Oct 27, 2020 (Introduction)
- Lecture #2, Nov 03, 2020 (Convex hull)
- Lecture #3, Nov 10, 2020 (Convex hull)
- Lecture #4, Nov 17, 2020 (Closest pair of points)
- Lecture #5, Nov 24, 2020 (Closest pair of points)
- Lecture #6, Dec 01, 2020 (Voronoi Diagram)
- Lecture #7, Dec 08, 2020 (Voronoi Diagram)
- Lecture #8, Dec 15, 2020 (Voronoi Diagram)
- Lecture #9, Jan 12, 2021 (Voronoi Games)
- Lecture #10, Jan 19, 2021 (Triangulations)
- Lecture #11, Jan 26, 2021 (Triangulations)
- Lecture #12, Feb 02, 2021 (Location Problems)
- Lecture #13, Feb 09, 2021
- Video of Lecture #13: [Youtube], [IBR]
- Slides of Lecture #13
- 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
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 Rieck. |
