| Carl Friedrich Gauß Faculty | Department of Computer Science

Seminar Algorithmik

SemesterSummer 2011 [ Other terms: Sommer 20 · Winter 19/20 · Sommer 19 · Winter 18/19 · Sommer 18 · Winter 17/18 · Sommer 17 · Winter 16/17 · Sommer 16 · Winter 15/16 · Sommer 15 · Winter 13/14 · Sommer 13 · Winter 12/13 · Sommer 12 · Winter 11/12 · Winter 10/11 · Winter 09/10 · Sommer 09 · Winter 08/09 ]
Module #INF-ALG-019
Event #INF-ALG-019
ProgrammesDiplom Informatik, Master Informatik, Master Wirtschaftsinformatik, Bachelor Informations-Systemtechnik, Master Informations-Systemtechnik, Bachelor Elektrotechnik, Master Elektrotechnik, Bachelor Informatik
IBR Group(s)ALG (Prof. Fekete)
PhotoProf. Dr. Sándor P. Fekete
+49 531 3913111
Room 335
PhotoDr. Christiane Schmidt
Ehemalige Wissenschaftliche Mitarbeiterin
PhotoDr. Alexander Kröller
Ehemaliger Juniorprofessor
Time & Place

Die Vorbesprechung findet am 06.04.2011 um 16.45 Uhr in Room 262A statt.

Die Abgabe der schriftlichen Ausarbeitung muss bis zum 16.06.2011 erfolgen.
In einer Blockveranstaltung am 30.06.2011 von 13:00 - 18:00 und am 01.07.2011 von 10:00-12:00 und 13:00-15:00 Uhr in Room 262A werden die Vorträge gehalten.

Datum Zeit Thema Seminarist Betreuer
30.06.2011 13:00 CGAL - Computational Geometry Algorithms Library Winfried Hellmann Tobias Baumgartner
30.06.2011 14:00 Visibility Graphs Pauline Dorda Christiane Schmidt
30.06.2011 15:00 Visibility Polygons Christian Mangelsdorf Christiane Schmidt
30.06.2011 16:00 Polygon Decomposition Marcel Kruse Max Pagel
30.06.2011 17:00 Art Gallery Jan Kokemueller Alexander Kröller
01.07.2011 10:00 Geometric Shortest Paths Christian Rieck Björn Hendriks
01.07.2011 11:00 Red-Blue Separation Sophia Scholtka Martin Lorek
01.07.2011 13:00 Minimum Stars and Maximum Matchings Hella Hoffmann Sándor Fekete
01.07.2011 14:00 Voronoi Games Raimar Buehmann Sándor Fekete

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.


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 Library

Fuer 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 Graphs

Fuer 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 Polygons

Der 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 Separation

Das 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 Paths

Das 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 Decomposition

Das 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 Maps

Shortest 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 Matchings

Das 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 Games

Das 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 Problems

Dieses 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

last changed 2011-06-27, 14:19 by Dr. Christiane Schmidt