Computational Geometry

Arbeitsbereich:	Bioinformatik
Dozent:	Dr. Olaf Delgado-Friedrichs
Sprechstunde:	Sand 14 Raum C309, Mo 16-18
Zeit:	Mi 13-15, Übungen Mi 12-13 und Mi 15-16
Umfang:	2(+1)
Ort:	Sand 6/7, kleiner Hörsaal (Raum 122)
Turnus:	traditionell 2-semestrig, zur Zeit 2-jährig
Pruefungsfach:	Theoretische und Praktische Informatik
Vorlesungsskript:	Kapitel 1-3 (Stand: 04.12.2002)
	Kapitel 4-6 (Stand: 29.01.2003, Neu ab Seite 75)

Übungsblätter:	Blatt 1 (17.10.2002)	Blatt 5 (13.11.2002)	Blatt 9 (08.01.2003)
	Blatt 2 (23.10.2002)	Blatt 6 (20.11.2002)	Blatt 10 (15.01.2003)
	Blatt 3 (30.10.2002)	Blatt 7 (04.12.2002)	Blatt 11 (22.01.2003) (Achtung: Aufgabe 2 korrigiert!)
	Blatt 4 (06.11.2002)	Blatt 8 (11.12.2002)	Blatt 12 (29.01.2003)
		Weihnachtsproblem (18.12.2002)

Code snippets:

Punkt in Kreis Test (Python)

Beschreibung:

In der algorithmischen Geometrie geht es um die Entwicklung effizienter Algorithmen für Probleme der diskreten und kombinatorischen Geometrie. Die betrachteten Objekte sind elementar - Punkte, Geraden, Strecken und so weiter. Komplexität entsteht erst aus dem Zusammenspiel vieler einfacher Elemente.

Der Schnittpunkt zweier Geraden zum Beispiel läßt sich leicht ausrechnen. Möchte man dagegen verstehen, wie ein Arrangement von hunderten oder gar tausenden von Geraden die Ebene zerteilt, so werden plötzlich geschickte Algorithmen und geeignete Datenstrukturen interessant.

Die Vorlesung diskutiert klassische Probleme wie Polygonzerlegung, konvexe Hüllen, Voronoi-Diagramme, Arrangements, Such- und Schnittprobleme und deren Anwendungen. Einige grundlegende Algorithmen und Paradigmen werden exemplarisch vorgestellt.

Voraussetzung:

Grundstudium (insbesondere Algorithmen und Datenstrukturen).

Literatur:

Franz Aurenhammer. Voronoi diagrams - a survey of a fundamental geometric data structure. ACM Computing Surveys, Vol. 23:345-405, 1991.
Mark de Berg et al. Computational Geometry - Algorithms and Applications (2nd edition). Springer-Verlag, 2000.
H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, 1987.
Steven Fortune. Voronoi diagrams and Delaunay triangulations. In D. Du and F. Hwang, editors, Computing in Euclidean Geometry, pages 193-233. World Scientific Publishers, 1992.
R. Klein. Algorithmische Geometrie. Addison-Wesley-Longman-Verlag, 1997.
D.T. Lee and F.P. Preparata. Computational geometry -a survey. IEEE Transactions on Computers, Vol. C-33(12):1072-1101, 1984.
K. Mehlhorn Data Structures and Algorithms. Springer-Verlag, 1994.
F.P. Preparata and M.I. Shamos. Computational Geometry: an Introduction. Springer-Verlag, 1985.
J. O'Rourke. Computational Geometry In C. Cambridge University Press, 1993.

Document Actions

Print this

Sections

Personal tools

Computational Geometry

Document Actions