Proseminar im WS 2005/2006:
Algorithmische Geometrie
Es gibt noch freie Plätze
!
Anmeldung: Am
18.10.2005 im Seminarraum MI 03.11.018 oder per E-Mail an Dmytro
Chibisov (chibisov@in.tum.de).
Zeit und Ort:
WS 2005/2006
Di., 14:00 - 15:15, Seminarraum MI 03.11.018
Beginn: 18.10.2005
Algorithmische Geometrie ist ein relativ junges Gebiet, das zwischen Mathematik
und Informatik angesiedelt ist und sich speziell mit den algorithmischen
Aspekten der geometrischen Fragestellungen beschäftigt. Zahlreiche Anwendungen
in Computergraphik und Computervision, computergestützten geometrischen
Modellierung und Design (CAM, CAD), Robotik und auf vielen anderen
Gebieten erfordern effiziente und robuste geometrische Algorithmen, deren
Analyse und Entwicklung die Zentralaufgaben der algorithmischen Geometrie
sind. Das Proseminar behandelt einige grundlegende geometrische Probleme
vom algorithmischen Standpunkt sowie ihre Anwendungen in der Industrie und
Wissenschaft und soll einen leichten Einstieg in die faszinierende Welt der
modernen Geometrie ermöglichen.
Voraussetzung für die Teilnahme am Proseminar sind neben Interesse an
Algorithmen und mathematischen Fragestellungen auch Englischkenntnisse, die
ausreichend für die Bearbeitung der ausschließlich englischsprachigen
Literatur sein sollen.
From Point Sets To Polytopes
1) Convex Hulls
Literture:
[PS]: Chapter 3, pp. 90-118;
2) Point Location Problem
Literature:
[PS]: Chapter 2.2, pp. 41-67;
3) Nearest Neighbour and Closest Pair Problem
Literature:
[PS]: Chapter 5, pp. 179-189;
4) All Nearst Neighbours and Voronoi Diagrams
Literature:
[PS]: Chapter 5, pp. 190-215
5) Euclidean Minimum Spanning Tree and Euclidean Traveling Salesman Problem
Literature:
[PS]: Chapter 6, pp. 219-226
Polygon Decomposition
6) Vertical Decomposition
Literature:
[BY]: Chapter 3, pp. 32-42
7) Planar Triangulation
Literature:
[PS]: Chapter 6.2, pp. 227-232
[BY]: Chapter 12, pp. 265-281
[RO]: Chapter 1.2, pp. 12-27
8) Convex Paritioning
Literature:
[RO]: Chapter 1.4, pp. 27-30
[???]: Chapter ?? (kommt noch)
9) An Application of Polygon Decomposition: Art Gallery Theorem
Literature:
[RO]: Chapter 1.1, pp. 1-15
Intersections and Arrangements
10) Hidden Line and Hidden Surface Problems: Computing Intersectons
Literature:
[PS]: Chapter 7, pp. 258-279
11) Intersections of Half-Planes: 2-Variable Linear Programming
Literature:
[PS]: Chapter 7, pp. 279-298
12) Arrangements of Line Segments in the Plane
Literature:
[BY]: Chapter 15, pp. 352-365
Literatur:
[PS] F. P. Preparata, M. I. Shamos: Computational Geometry: An Introduction,
Springer-Verlag, 1985
[BY] J-D. Boissonnat, M. Yvinec: Algorithmic Geometry, Cambridge University
Press, 1998
[RO] J. O'Rourke: Art Gallery Theorems and Algorithms, Oxford University Press,
1987
Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben,
wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich
aus gewichteten Einzelnoten zusammen):
| Probevortrag (ohne Bewertung) |
Der Probevortrag erfolgt spätestens zum angegebenen Termin
beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien
oder ähnliche Präsentationshilfsmittel und die Erstfassung
der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin
beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
|
| Seminarvortrag (in mindestens zufriedenstellender
Qualität) |
Der Seminarvortrag ist zum festgelegten Termin zu halten und
dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht
akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen
werden. |
| Seminararbeit (in mindestens zufriedenstellender
Qualität) |
Die Endfassung der Seminarbeit muss zum Zeitpunkt des Vortrags
als TeX-Datei und Postscript-Datei abgegeben worden sein. Der Umfang
der Seminararbeit beträgt 8 (+/- 1) Seiten (ohne Literaturverzeichnis)
im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten).
|
Ablauf der Vorbereitung
Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen
werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders
mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt
dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:
| bis 4 Wochen vor dem Vortrag |
|
erstes Treffen mit dem Betreuer (vor dem Treffen ist
die Literatur bereits zu lesen); die genauen Vortragstermine werden noch
bekannt gegeben; |
| bis 2 Wochen vor dem Vortrag |
|
Gliederung des Vortrags und der Ausarbeitung mit dem Betreuer
besprechen; |
| bis 1 Woche vor dem Vortrag |
|
Probevortrag vor den Betreuer; fertige Folien und vollständige
erste Version der Ausarbeitung mit dem Betreuer abstimmen; |
| bis Ende des Semesters |
|
Abgabe der endgültigen Version der Ausarbeitung beim Betreuer.
|
Hinweise zur Anfertigung einer Seminararbeit
 |
Die Seminararbeiten werden nach der letzten Seminarveranstaltung
gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine
einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit
dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien
zu beachten: |
|
- Es ist der LNCS-Style
(die Datei
llncs.cls) des Springer-Verlages zu verwenden.
- Der folgende Rahmen ist zu verwenden (seminararbeit.tex).
Dabei dürfen die Seitengröße und der Font nicht
verändert werden.
- Ein Beispiel kann in der Datei example.tex gefunden
werden (das Bild example.eps wird
eingebunden)
- Die Ausarbeitung soll auf die verwendete Literatur
verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer
eigenen Datei zu speichern (hier die zum Beispiel gehörende
Datei: example.bib).
|
| |
Bei Fragen zu LaTeX sei einerseits auf die folgenden Links
hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw.
Literaturangaben gebeten werden: |
|
|
| |
Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden
sie hier.
|
| |
Informationen zur Installation von LaTeX unter Windows
finden Sie hier.
|
Hinweise zur Gestaltung der Seminarvorträge
Weitere Auskünfte bei Dmytro Chibisov.
Dmytro Chibisov , 2
July, 2005.
