UNI Logo Bilder Heinz Nixdorf Institut
Algorithmen und Komplexität
Prof. Dr. math. Friedhelm Meyer auf der Heide
HNI Logo
Home > Fachgruppen > Prof. Dr. math. Friedhelm Meyer auf der Heide > Lehre > Algorithmische Geometrie
Wintersemester 2011/12, Proseminar
Algorithmische Geometrie

Inhalt dieses Proseminars ist eine Einführung in die algorithmische Geometrie. Wir werden als Grundlage einzelne Kapitel aus verschiedenen Büchern verwenden.

 Computational Geometry: Algorithms and Applications,
Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars;
Springer, Berlin; 2008

Algorithmische Geometrie: Grundlagen, Methoden, Anwendungen,
Rolf Klein;
Springer, 2005.

Computational Geometry: An Introduction,
Franco P. Preparata;
Springer, 1993

 Handbook of Discrete and Computational Geometry
Jacob E. Goodman, Joseph O'Rourke
CRC Press, 1997.

Themen

Einführung, Schnitte von Liniensegmenten, Polygon Triangulierung, Lineare Programmierung, Orthogonale Bereichsabfragen, Punktlokalisierung, Voronoi Diagramme, Arrangements und Dualität, Delaunay Triangulierungen, Weitere geometrische Datenstrukturen, Konvexe Hüllen (3D), Binäre Raumaufteilungen, Bewegungsplanung, Quadtrees, Sichtbarkeitsgraphen, Simplex Bereichssuche.

Termine

Vorbesprechung, erstes Treffen und Themenvergabe: Mo, 10. Oktober 2011 16:15 - 18:00 Uhr , F1.310

Voraussetzungen

  • Grundstudiumskenntnisse, Vorlesung Algorithmen und Komplexität ist vorteilhaft.

Scheinerwerb

  • erfolgreicher Vortrag, gelungene Ausarbeitung, regelmäßige Teilnahme und Mitarbeit beim Seminar
  • Modul II.5.1

Vergabe der Themen und Anmeldung

Die Themen werden auf dem ersten Treffen an die anwesenden Studierenden vergeben. Reservierungen oder Vorbelegungen von Themen sind nicht möglich. Sie müssen sich vor dem ersten Treffen in  PAUL anmelden. Informationen zu PAUL gibt es  hier. Nicht angemeldete Studierende werden nicht berücksichtigt. Die Reihenfolge der Anmeldung hat keine Bedeutung. Sollten sich mehr Studierende für das Proseminar interessieren als Plätze vorhanden sind, so wird die Auswahl nach dem Studienfortschritt getroffen. Beim Proseminar wäre bspw. der fertige Erste Studienabschnitt Voraussetzung.

Hinweise zur Ausarbeitung von Seminaren


Elektronisches Format der Ausarbeitung

Die Ausarbeitung des Seminars wird in  LaTeX mit dem  svmult-Style (siehe Paket  Beitragswerke, Konferenzbände) des  Springer-Verlags erstellt. Es wird ein Gesamtband erstellt, ein Beispiel sehen Sie  hier. Die LaTeX-Sourcen UND ein fertiges pdf Ihrer Ausarbeitung schicken Sie als zip-Datei per E-Mail an Matthias Fischer ( mafi(at)upb.de). Bitte geben Sie in Ihrer Ausarbeitung keine Matrikelnummer an. Beachten Sie folgende LaTeX-Spielregeln:

  • Das Dokument wird nur mit pdflatex kompiliert. Bilder werden dementsprechend direkt mit pdf, jpg oder png eingebunden. DVI-LaTeX wird nicht erzeugt.
  • Es gibt nur eine .tex Datei für die gesamte Ausarbeitung. Starten Sie am besten mit der im svmult Paket angegebenen Datei "author.tex". Alle Bilder und die Tex-Datei liegen im selben Verzeichnis. Die oberste Gliederungsebene ist \section.
  • Um alle selbst definierten Kommandos, Labels und Referenzen eindeutig zu definieren, bekommt jeder Autor (Beispiel: Matthias Fischer) einen eindeutigen Präfix (Beispiel: MaFi). Kommandos, Labels und Referenzen bestehen dann aus Präfix gefolgt von der selbst gewählten individuellen Bezeichung (Beispiel: TollesLabel). Das fertige Label sieht also so aus: \label{MaFiTollesLabel}.
  • Der Name der LaTeX-Datei (es gibt nur eine text-Datei!) besteht nur aus dem Präfix: "MaFi.tex". Die Namen der Bilddateien bestehen aus dem Päfix und einem individuellem Teil (Beispiel: MeinBild): Der fertige Name für eine Bilddatei sieht also so aus: "MaFiMeinBild.png"
  • Nach \maketitle wird der Abstract in svmult mit \begin{abstract} \end{abstract} erfasst, ihm folgt das lokale Inhaltverzeichnis: \hrule \setcounter{minitocdepth}{2} \dominitoc
  • Wir verwenden durchgängig die svmult theorem-Umgebungen. Die Option "nospthms" und das Paket "amsthm" findet keine Verwendung. Das Paket "amsthm" verträgt sich nicht mit "svmult".
  • Wir verwenden kein BibTex, die Literatur wird so wie im svmult Template „referenc.tex“ angegeben, jedoch nicht in 2 Dateien, sondern zusammen mit dem Haupttext in einer Datei. Der Inhalt von "referenc.tex" sollte daher ans Ende der Autor-Datei kopiert werden. Die Referenzen werden, wie im svmult Template "referenc.tex" gezeigt, angegeben. Es ist einheitlich zur Formatierung der Einträge der in „reference.tex“ angegebene Stil (Autor, Jahr, Titel, ....) zu verwenden.
  • Zur Formatierung der Pseudocode-Algorithmen verwenden wir "algorithmicx" inkl. der floating Umgebung "algorithm" aus "Algorithms". Empfehlenswert ist mit dem bereits vordefinierten Befehlen im Paket "algpseudocode" zu starten. Das Paket "algorithmic" aus "Algorithms" verwenden wir nicht. Alternativ zu "algorithmicx" können die Algorithmen auch mit "listings" oder "verbatim" erstellt werden. Auch das Paket "algorithm2e" wird wegen Inkompatiblität nicht verwendet.
  • Zusammen mit dem im svmult Beispiel "author.tex" angegebenen Header
    \documentclass[deutsch]{svmult} \usepackage{makeidx} \usepackage{graphicx} \usepackage{multicol} \usepackage[bottom]{footmisc} \makeindex
    können dann noch die folgenden Pakete verwendet werden; andere sind nicht erlaubt:
    \usepackage[latin1]{inputenc} \usepackage[ngerman]{babel} \usepackage[T1]{fontenc} \usepackage{amsmath, amssymb, amsfonts, amscd} \usepackage{algpseudocode} \usepackage{algorithm} \usepackage{listings} \usepackage{verbatim}
  • Die in svmult effektiv beschreibbare Seitengröße ist für unsere Verwendung zu klein. Die angepasste Form erhalten Sie hier. Tauschen Sie ihre svmult.cls dagegen aus.


Nach oben