Seminar Algorithmische Geometrie
Algorithmische Probleme auf Polygonen
Sommersemester 2008
Stefan Schirra
Das Seminar wird als Blockseminar durchgeführt und wird am
20. und 21. Juni in G29-335
stattfinden, siehe auch
Stundenplan.
Die Vorbesprechung mit Themenvergabe fand am
Mi. 9. April um 14:00 Uhr in G29-224 statt.
Im Seminar werden wir uns Algorithmen für einfache Polygone in der
Ebene anschauen, beispielsweise
Boolsche Operationen auf Polygonen,
Sichtbarkeitsfragen in Polygonen, z.B. Art-Gallery Theoreme,
Constructive-Solid-Geometry Darstellung,
Medial-Axis Berechnung,
Vereinfachen von Polygonen (Kartographie),
Ähnlichkeit und Geometrisches Matchen von Polygonen,
Zerlegung in konvexe Teile, insbes. Triangulierung,
Berechnung grö฿ter k-Ecke, die innerhalb eines gegebenen Polygons liegen,
Polygonrekonstruktion aus Punktdaten,
Minkowski Summen von Polygonen,
Polygone, die Anordnungen von Geraden erzeugen,
konvexe Hülle von Polygonen und
Point-in-Polygon Testing.
Schedule (45 min Vortrag + 15 min Diskussion):
Freitag, 20. Juni
|
15:15 - 16:15
|
Steffen Ernst
Dobkin, Guibas, Hershberger, Snoeyink; An Efficient Algorithm for Finding the CSG Representation of a Simple Polygon &
Walker, Snoeyink; Practical Point-in-Polygon Tests Using CSG Representations of Polygons
|
|
16:25 - 17:25
|
Liu Manru
Edelsbrunner, Guibas, Stolfi; Optimal Point Location in a Monotone Subdivision
|
|
17:35 - 18:35
|
Jan Heidel
Estowski, Mitchell; Simplifying a Polygonal Subdivision While Keeping it Simple
|
|
18:45 - 19:45
|
Haibing Yang
Efrat, Guibas, Har-Peled, Mitchell, Murali; New Similarity Measures between Polylines with Applications in Morphing and Polygon Sweeping
|
|
Samstag, 21. Juni
|
09:15 - 10:15
|
Konrad Kügler
Ghosh, Mount;An Output-Sensitive Algorithm for Computing Visibility Graphs
|
|
10:25 - 11:25
|
Li Yuexiao
Bose, Everett, Wismath;Properties of Arrangement Graphs & Mumford, Scharf, Scherfenberg; Inducing Polygons of Line Arrangements
|
|
11:35 - 12:35
|
Kai Dannies
Lien, Amato;Approximate Convex Decomposition of Polygons
|
|
Zuhörer sind übrigens immer willkommen!
|
)
ist eine inzwischen in die Jahre gekommene Anleitung zur Vortragsvorbereitung,
die aber immer noch sehr nützliche Infos bietet. Man beachte, dass sich
die Anleitung auf kürzere Vorträge (20- 30 min) bezieht;
ein wenig mehr Zeit für Details haben wir schon.
Natürlich muss man auch die Hinweise zur Medienwahl auf die neuen
Gegebenheiten übertragen (damals waren Beamer noch eine Rarität).
