Seminar Algorithmische Geometrie

Voronoi Diagramme

Sommersemester 2007

Stefan Schirra
Ivo Rössling

Stundenplan

Das Seminar wird als Blockseminar durchgeführt und findet statt am

Fr. dem 29. und Sa. dem 30. Juni in G29-335
Eine Vorbesprechung mit Themenvergabe fand am Mo. 16. April um 13:30 Uhr in G29-224 statt.

Im Seminar werden wir uns verschiedene Varianten von Voronoi Diagrammen und Algorithmen zur Berechnung von Voronoi Diagrammen anschauen. Voronoi Diagramme sind Unterteilungen der Ebene (bzw. des Raums) in Nächste-Nachbar-Regionen.

Schedule (45 min Vortrag + 15 min Diskussion):

Freitag, 29. Juni

13:15 - 14:15
C. Steinberg
F. Aurenhammer; Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure (Part 1). ACM Computing Surveys, 1991.

14:15 - 15:15
M. Jantowski
P.J. Green and R. Sibson; Computing Dirichlet tessellations in the plane.
The Computer Journal, 1978.

15:30 - 16:30
F. Krüger
L. Guibas, J. Stolfi; Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM ToG, 1985.

16:30 - 17:30
H. Hugenberg
S. Fortune; A Sweepline Algorithm for Voronoi Diagrams.
Algorithmica, 1987.

17:45 - 18:45
L. Übernickel
K.Q. Brown; Voronoi Diagrams from Convex Hulls.
IPL, 1979.

18:45 - 19:45
C. Hütter
H. Edelsbrunner, R. Seidel; Voronoi Diagrams and Arrangements.
SoCG 1985.

Samstag, 30. Juni

8:30 - 9:30
V. Laube
F. Aurenhammer, H. Edelsbrunner; An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 1984.

9:30 - 10:30
K. Breshnyev
L. Mu; Polygon Characterization with the Multiplicatively Weighted Voronoi Diagram.
The Professional Geographer, 2004.

10:45 - 11:45
V. Yuskevich
F. Aurenhammer; Power Diagrams: Properties, Algorithms and Applications.
SIAM J.Comp. 1987.

11:45 - 12:45
R. Harbich
K.Mehlhorn, S. Meiser, C. O'Dunlaing; On the Construction of Abstract Voronoi Diagrams. Discr. & Comp. Geom., 1991

Zuhörer sind übrigens immer willkommen!

Hinweis: "How to present a paper in theoretical computer science" (

) 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).

Webmaster -