| Semester | Winter 2023/2024Summer 2023Winter 2022/2023Summer 2022Winter 2021/2022Summer 2021Winter 2020/2021Summer 2020Winter 2019/2020Summer 2019Winter 2018/2019Summer 2018Winter 2017/2018Summer 2017Winter 2016/2017Summer 2016Winter 2015/2016Summer 2015Winter 2013/2014Summer 2013Winter 2012/2013Summer 2012Winter 2011/2012Winter 2010/2011Winter 2009/2010Summer 2009Winter 2008/2009 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Module # | INF-ALG-019 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Event # | INF-ALG-019 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Programmes | Diplom Informatik, Computer Science Master, Business Information Systems Master, Computer and Communication Systems Engineering Bachelor, Computer and Communication Systems Engineering Master, Electrical Engineering Bachelor, Electrical Engineering Master, Computer Science Bachelor | ||||||||||||||||||||||||||||||||||||||||||||||||||
| IBR Group | ALG (Prof. Fekete) | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Type | Seminar | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Lecturer | |||||||||||||||||||||||||||||||||||||||||||||||||||
| Assistants | Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin Dr. Alexander Kröller Ehemaliger Juniorprofessor | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Credits | 4 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Hours | 0+2 | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Time & Place | Die Vorbesprechung findet am 06.04.2011 um 16.45 Uhr in Room 262A statt. ACHTUNG NEU:
| ||||||||||||||||||||||||||||||||||||||||||||||||||
| Certificates | Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von der aktiven Teilnahme am Seminar sowie der Qualität des Vortrages und der Ausarbeitung bestimmt. Vortrag: Ihr Vortrag sollte ca. 40 Minuten dauern. Das Medium ist frei, Sie können also Tafel, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, oder was auch immer Sie sinnvoll finden, einsetzen. Natürlich sollten Sie bei exotischen Wünschen diese erstmal mit dem Betreuer klären, und unbedingt auch Programm-, Programmversions- und sonstige Kompatibilitätsfragen besprechen. Ausarbeitung: Schreiben Sie eine Ausarbeitung, die Sie zwei Wochen vor dem Vortrag abgeben. Die Ausarbeitung soll ca. 10 Seiten lang sein. Generell interessiert uns aber, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Mehr als zehn Seiten sollten es dennoch nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. | ||||||||||||||||||||||||||||||||||||||||||||||||||
| Content | Das Seminar Algorithmik im Sommersemester 2011 beschäftigt sich mit einer Reihe von aktuellen Themen aus dem Gebiet der algorithmischen Geometrie. Voraussetzungen fuer die Bearbeitung der Themen sind jeweils direkt beim Thema aufgefuehrt. | ||||||||||||||||||||||||||||||||||||||||||||||||||
Thema 1: CGAL - Computational Geometry Algorithms LibraryFuer dieses Thema soll Cgal vorgestellt werden ( cgal ):The goal of the Cgal Open Source Project is to provide easy access to efficient and reliable geometric algorithms in the form of a C++ library. The Computational Geometry Algorithms Library offers data structures and algorithms like triangulations, Voronoi diagrams, Boolean operations on polygons and on polyhedra, arrangements of curves, mesh generation, geometry processing, convex hull algorithms, to name just a few. All these data structures and algorithms operate on geometric objects like points and segments, and perform geometric tests on them. These objects and predicates are regrouped in Cgal Kernels. Finally, the Cgal Support Library offers geometric object generators and spatial sorting functions, as well as a matrix search framework and a solver for linear and quadratic programs. It further offers interfaces to third party software such as the Gui libraries Qt, Geomview, and the Boost Graph Library. Thema 2: Visibility GraphsFuer dieses Thema sollen Visibility Graphs sowie Algorithmen zu deren Berechnung dargestellt werden:The visibility graph of a polygon P with or without holes is the undirected graph of the visibility relation on the vertices of P. The visibility graph of P has a node for every vertex of P and an edge for every pair of visible vertices in P. Thema 3: Visibility PolygonsDer Begriff des Visibility Polygons soll erläutert werden und Algorithmen zur Berechnung von Visibility Polygonen sollen vorgestellt werden:The visibility polygon V(Q) of a point q in a simple polygon P is the set of all points of P that are visible from q. Thema 4: Red-Blue SeparationDas Red-Blue Separation Problem und Algorithmen fuer dieses Problem sollen vorgestellt werden:The Red-Blue Separation Problem: We are given finite sets R and B of points in the euclidean plane. The task is to find a simple polygon that separates the red points (points in R) from the blue points (points in B). We want to find a polygon P such that its perimeter is minimal. Voraussetzung: Algorithmische Geometrie Thema 5: Geometric Shortest PathsDas Geometric Shortest Paths Problem und Algorithmen fuer dieses Problem sollen vorgestellt werden:For a graph embedded in the plane find the shortest path between two verties s and t in the graph. Voraussetzung: Netzwerkalgorithmen Thema 6: Polygon DecompositionDas Problem der Polygon Decomposition wird vorgestellt, und Algorithmen fuer die Zerlegung fuer einen/einige Faelle vorgestellt:A given polygon P should be decomposed into simpler components, in most applications we want a decomposition that is minimal in some sense. Often, we seek to decompse the polygon into the minimum number of component. A possible type of subpolygons for the decomposition are convex polygons. Thema 7: Shortest Path MapsShortest Path Maps und deren Berechnung werden vorgestellt:Given a polygon or a polygonal demain, find the shortest path between two points s and t. Voraussetzung: Algorithmische Geometrie Thema 8: Minimum Stars and Maximum MatchingsDas Problem Minimum Stars soll vorgestellt und die Beziehung zu Maximum Matching betrachtet werden:We consider “minimum stars” which are defined by a center chosen from a given point set, such that the total geometric distance min|St| to all the points in the set is minimized. If the center point is not required to be an element of the set (i. e., the center may be a Steiner point), we get a “minimum Steiner star”, of total length min|StSt|. As a consequence of triangle inequality, the total length max|Mat| of any maximum matching is a lower bound for the length min|StSt| of a minimum Steiner star, which makes the ratio min|StSt|/max|Mat| interesting in the context of optimal communication networks. Voraussetzung: Algorithmische Geometrie Thema 9: Voronoi GamesDas Voronoi Game soll vorgestellt, dieses Paper basiert auf einem wissenschaftlichen Artikel (pdf):We consider the one-roundVoronoi game, where the first player (“White”, called “Wilma”) places a set of n points in a rectangular area Q of aspect ratio ρ \leq 1, followed by the second player (“Black”, called “Barney”), who places the same number of points. Each player wins the fraction of Q closest to one of his points, and the goal is to win more than half of the total area. This problem has been studied by Cheong et al. who showed that for large enough n and = 1, Barney has a strategy that guarantees a fraction of 1/2+α, for some small fixed α. We resolve a number of open problems raised by that paper. In particular, we give a precise characterization of the outcome of the game for optimal play: We show that Barney has a winning strategy for n /geq 3 and ρ > \sqrt(2)/n, and for = 2 and ρ > \sqrt(3)/2. Wilma wins in all remaining cases, i.e., for n \geq 3 and ρ \leq \sqrt(2)/n, for n = 2 and ρ \leq \sqrt(3)/2, and for n = 1. We also discuss complexity aspects of the game on more general boards, by proving that for a polygon with holes, it is NP-hard to maximize the area Barney can win against a given set of points by Wilma. Voraussetzung: Algorithmische Geometrie Thema 10: Exact Solutions and Bounds for General Art Gallery ProblemsDieses Thema basiert auf einem wissenschaftlichen Artikel ( pdf):The classical Art Gallery Problem asks for the minimum number of guards that achieve visibility coverage of a given polygon. This problem is known to be NP- hard, even for very restricted and discrete special cases. For the case of vertex guards and simple orthogonal polygons, Cuoto et al. have recently developed an exact method that is based on a set cover approach. For the general problem (in which both the set of possible guard positions and the point set to be guarded are uncountable), neither constant-factor approximation algorithms nor exact solution methods are known. We present a primal-dual algorithm based on linear programming that provides lower bounds on the necessary number of guards in every step and|in case of convergence and integrality|ends with an optimal solution. We describe our implementation and give results for an assortment of polygons, including non-orthogonal polygons with holes. Voraussetzung: Algorithmische Geometrie, Mathematische Methoden der Algorithmik | |||||||||||||||||||||||||||||||||||||||||||||||||||