Softwareprojekt über Anwendungen effizienter Algorithmen - WS 2009/10

Termine

Dienstags, 16 Uhr, Takustraße 9, Seminarraum 055

Dienstag, 13. 10.: Vorbesprechung und Themenvergabe
Dienstag, 20. 10.: Themenbesprechungen, eventuell weitere Themenvergabe

16:25–16:50: Team 1A + 1B
16:50–17:10: Team 5
17:10–17:30: Team 4A + 4B
17:30–17:50: Team 2

Dienstag, 27. 10.: Themenbesprechungen, erste Projektvorstellungen?
- Tas Sóti vom Saros-Team der Arbeitsgruppe Software Engineering: Das Eclipse-Plugin Saros zur verteilten Paarprogrammierung
Dienstag, 3. 11.: kein Treffen
Dienstag, 10. 11.: Präsentationen der Aufgabenstellungen, Abschlusspräsentation vom vorigen Semester:
- Patrick Oliver Einig, Robert Fels, Franz Gatzke, Norman Warnatsch: Zerlegung eines Bereichs in zwei kongruente Polygone
- David Breßler, Roland Günther, Max Merkx, Stefan Nolte, Patrick Remmler (Team 4A): Durchschieben eines Körpers durch sich selbst.
- Jens Hantke, Eva Jockwer, Jennifer Möwert, Holger Solinski (Team 4B): Durchschieben eines Körpers durch sich selbst.
- Team 1B: Kinetische Kollisionserkennung mit Pseudotriangulierungen.
Dienstag, 17. 11.: Präsentationen der Aufgabenstellungen,
- Team 1A:
- Team 5:
- Team 2:
Dienstag, 2. 2. 2010: Abschlusspräsentation:
Dienstag, 16. 2. 2010: Weitere Abschlusspräsentation:

Inhalt

Die Teilnehmer sollen in Teams Verfahren aus verschiedenen Gebieten der effizienten Algorithmen implementieren und damit experimentieren. Eine Ausweitung der Projekte in Bachelor-, Studien-, Diplom- oder Masterarbeiten ist möglich.

Das Softwareprojekt steht sowohl Bachelor- als auch Master-Studenten offensteht, und es sollen sich gemischte Teams unter der Leitung von ein oder zwei Master- oder Diplomstudenten bilden.

Ablauf

Eine Arbeitsgruppe von typischerweise 5–10 Personen (je nach Umfang der Aufgabe) kümmert sich um ein Thema, liest die dazupassende Literatur, teilt sich die Aufgabe in geeignete Teile ein, verteilt die Aufgaben und Rollen unter sich, und legt in Absprache mit mir das Ziel des Praktikums fest. Zu Beginn des Semesters (in den ersten drei Wochen, d.h. bis Montag, den 9. November) werden diese Ziele und Zwischenziele, wenn möglich mit Terminvorgaben, schriftlich festgehalten, stichwortartig auf 1/2 bis 1 Seite Länge, und die Gruppe präsentiert ihr Projekt. Im Laufe des Semesters werden laufend, je nach Fortschritt, Zwischenergebnisse der verschiedenen Projekte präsentiert und diskutiert. Am Ende steht eine Abschlusspräsentation, sowie ein Abschlussbericht von etwa 10 Seiten Länge, der alles Wichtige über die Praktikumsarbeit, und insbesondere, was dabei gelernt wurde, enthalten sollte: Wurden die ursprünglichen Ziele des Praktikums erreicht? Welche Schwierigkeiten sind aufgetreten? Welche alternativen Lösungen wurden verworfen? Was hätte man anders oder besser machen können?

Teams

Team 1A (statisch): Alexander Bach, Christoph Godglück, Martin Lange, Tobias Tenbusch
Team 1B (dynamisch): Mathias Hecht, Jaehwan Ji, Sebastian Oliver Kalwa, Ralf Müller-Zimmermann, Benjamin Valentin, Michael Zettelmann, Sebastian Ziller
Team 2: Stefan Friesel, David Knötel, Mohsen Taheri
Team 4A: David Breßler, Roland Günther, Max Merkx, Stefan Nolte, Patrick Remmler
Team 4B: Jens Hantke, Eva Jockwer, Jennifer Möwert, Holger Solinski
Team 5: Benjamin Eckstein, Antonia Kresse, Piotr Wesolek, Martin Weigelt

Themen

Balancierte geodätische Triangulierungen als Datenstruktur für Kollisionserkennung bei der Bewegungssimulation für statische (für 3–4 Personen) und dynamische (für 4–6 Personen) Umgebungen.
- Implementierung von Datenstrukturen
- Zum Beispiel zu Simulation einer Billardkugel in einem polygonalen Bereich
- Literatur: B. Chazelle, H. Edelsbrunner, M. Grigni, L. J. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations. Algorithmica, 12:54–68, 1994. M. T. Goodrich and R. Tamassia. Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations. Journal of Algorithms, 23:51–73, 1997. P. Agarwal, J. Basch, L. Guibas, J. Hershberger, and L. Zhang. Deformable free space tilings for kinetic collision detection. International Journal of Robotics Research, 21:179–197, 2002. Vorläuferarbeit: J. Basch, J. Erickson, L. J. Guibas, J. Hershberger, and L. Zhang. Kinetic collision detection for two simple polygons. In Proc. 9th ACM-SIAM Sympos. Discrete Algorithms, 102–111, 1999.
Unterteilungs-Überzusammensetzungs-Algorithmus für Nullstellen von Polynomen (für 3–4 Personen) und zum Schnitt von Bézier-Kurven (insgesamt für 5–6 Personen)
- numerisches Rechnen mit Polynomen; Beachtung von Genauigkeit
- Literatur: Günter Rote: Curve intersection by the Subdivision-Supercomposition Method, Mai 2008; dazu Vortragsfolien. A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt and N. Wolpert: A Descartes Algorithm for Polynomials with Bit-Stream Coefficients. 8th Internat. Workshop on Comp. Algebra in Scientific Computing (CASC 2005), Springer LNCS 3718, pp. 138–149. Arno Eigenwillig: Experiments with the Bit-Stream Descartes Method.
Verbesserte Realisierung von 3-Polytopen mit kleinen Koordinaten (für 3–4 Personen)
- schlechte Beispiele von André Schulz; Dodekaeder
- Literatur: André Schulz: Lifting Planar Graphs to Realize Integral 3-Polytopes and Topics in Pseudo-Triangulations (Dissertation)
Passt ein regelmäßiges Ikosaeder durch ein gleich großes Ikosaeder? (für 3–5 Personen)
- geometrische Konstruktionen im Raum
- Man kann in einen Würfel ein Loch bohren, durch das man einen gleich großen Würfel hindurchschieben kann. Geht das auch mit anderen Körpern?
- Algorithmus für den Test, ob ein konvexes Polygon in ein anderes hineinpasst: Bernard Chazelle, The polygon containment problem. Advances in Computing Research, Vol. I: Computational Geometry, (F.P. Preparata, Ed.), JAI Press, 1983, S. 1–33. Siehe auch F. Avnaim and J. D. Boissonnat, Polygon placement under translation and rotation, 5th Annual Symp. on Theoretical Aspects of Computer Science, Bordeaux, February 11–13, 1988, Lectures Notes in Comp. Science 294, Springer-Verlag, New-York, 1988, 322–333.
  Roman Waupotitsch: Rotating a convex polygon in a convex polygon, Diplomarbeit, Technische Universität Graz, 1988.
  K. A. Post. Triangle in a triangle: On a problem of Steinhaus. Geometriae Dedicata 45 (1993), 115–120. doi:10.1007/BF01667408
Zerlegung eines Bereichs in zwei kongruente Polygone (für 3–4 Personen)
- Vergleich verschiedener Algorithmen-Varianten
- Umgang mit ungenauen Daten
- Literatur:
  Dania El-Khechen, Thomas Fevens, John Iacono und Günter Rote: Partitioning a polygon into two mirror congruent pieces. In: Proceedings of the 20th Canadian Conference on Computational Geometry, Montréal, August 13–15, 2008, pp. 131–134. Kurzversion, Langversion
  G. Rote: Decomposition of a polygon into two congruent pieces. (unvollendetes Manuskript)
  Kimmo Eriksson: Splitting a polygon into two congruent polygons, American Mathematical Monthly 103 (1996), 393–400.
  A. M. Bruckstein and D. Shaked Crazy cuts: dissecting planar shapes into two identical parts, in: Mathematics of Surfaces XIII, Lecture Notes in Computer Science, Volume 5654 (2009), Springer Berlin/Heidelberg, pp. 75–89
Rhombuszerlegungen in drei Dimensionen (für 3–4 Personen)
- kombinatorisches Aufzählen, Mengenüberdeckungsproblem
- Notwendige Bedingung für die Existenz einer gemischten Rhombuszerlegung in einem regelmäßigen Tetraeder (siehe Federico Ardila und Sara Billey, Flag arrangements and triangulations of products of simplices, Advances in Mathematics, 214 (2007) 495–524, Frage 6.1 und Vermutung 7.1; siehe z. B. auch Francisco Santos, The Cayley Trick and triangulations of products of simplices. http://arxiv.org/abs/math.CO/0312069)

Günter Rote