Algorithmische Geometrie

Proseminar, Summer Term 2016

Will be held in German

Content of this Proseminar is an introduction to computational geometry. We will work with individual chapters from different books.

Keywords: Introduction, sections of line segments, polygon triangulation, linear programming, orthogonal range queries, point location, Voronoi diagrams, arrangements and duality, Delaunay triangulations, more geometric data structures, convex hulls (3D), binary space partitioning, motion planning, quadtrees, visibility graphs, simplex range search.

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

Lecturer

  • Ulf-Peter Schroeder, Matthias Fischer

Modul

  • Modul II.5.1

Dates

  • Time and room see PAUL
  • First Meeting (assignment of topics)
    Date: 15.4.2016

Topics and Registrations

The topics are given in the first meeting. Reservations or defaults of issues are not possible. Your must register yourself in PAUL to attend this seminar. Unregistered students are not considered. The order of registration is of no importance. If there are more students interested in the seminar than places available, the selection of participants is made according to the study progress. For the seminar, e.g., the requirement would be the completed bachelor.

Grading

We will grade the following parts of this course individually:

  • quality of the presentation
  • quality of the essay

You have to pass (i.e., 4.0 or better) each part individually to pass this course. Note that commitment, diligence, and compliance with our deadlines will be taken into account.

We expect your active participation (as opposed to mere attendance) at all presentations of this seminar.

Remarks

General

Each topic has one or several references that should be understood as starting points for your research. Hence, it is very likely that you will need further papers or textbooks to fully understand your topic. The actual content of your seminar thesis as well as your seminar talk should be discussed with your adviser.

It is your responsibility to contact your adviser and schedule appointments with them early enough. We strongly recommend you to discuss questions regarding the topic, the composition, and the structure of your written seminar thesis with your adviser. The same holds for your seminar talk. Note that finding an appointment directly before your thesis' submission or seminar talk cannot be guaranteed, since the advisers need to arrange their appointments with their own teaching and research.

If you are looking for additional research papers, the following links might be helpful:

Seminar Thesis

We expect an essay of length 12 to 20 pages written according to the standards of a scientific paper. A simple summary of the referenced literature is insufficient. We expect you to identify the important ideas and proofs of the referenced literature and present them in a correct and appropriate way. The mandatory typesetting for your thesis is LaTeX (see below for details). All citations must be marked as such and referenced with their origin. Plagiarism directly leads to failure of the seminar. Note that plagiarism not only includes copies from the original literature, but also copies from other authors (e.g., other seminar theses) or translations of them.

Title and Abstract

Create a brief abstract that summarizes the problem and the main results. An abstract is kept short (typically 10-20 lines). Also make up a title for your thesis (note that this is not necessarily the title of the used literature or the title from our topic list). It is important to make your own reasoning about a title that describes the thesis best from your point of view.

References

Each thesis contains a reference list that contains at least the literature used in your thesis. In the digital libraries of DBLP, ACM, IEEE, or Springer you can find detailed literature reference information. For conferencing proceedings or journals ALWAYS specify the pages. For journals, additionally provide volume and journal number. Do not rely on the authors to do their references correct (e.g., reference list in a paper or at the author's website). Sometimes this references are wrong are incomplete. Also do not rely on search engines like CiteSeer or Google Scholar: always verify the correctness and completeness of your references. Especially, it is insufficient if you only provide links to the papers or citations in the web.

Further Reading

For further reading we advice

Submission of your Seminar Thesis

The thesis has to be created with LaTeX using our customized version of the svmult-Style package (Version 5.4 of the package Contributed Books, Proceedings and similar with changes as explained below) by Springer. We will create a complete volume consisting of all submissions. An example can be found here. You have to submit the LaTeX sources AND a complete pdf of your seminar thesis by mail. The mail shall contain only one zip or tar.gz file with these data and must be sent to Matthias Fischer. Please do NOT include your matriculation number in your thesis. For the LaTeX document you have to follow the following rules of the game:

  • The document must be compiled with pdflatex. Hence, pictures must to be included as pdf, jpg or png.
  • There is only one "*.tex" file for your complete seminar thesis.
  • For an easy start: use the file "author.tex" from the svmult-package and extend it. All pictures and the LaTeX file itself have to be contained in the same directory.
  • Your file must be encoded in UTF-8.
  • Your highest breakdown-level is \section. (Thus, you can use \section, \subsection, \subsubsection, \paragraph, etc.)
  • To distinguish all self-defined commands, labels and references, each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi".)
  • Each command, label and reference consists of the prefix, followed by an individual identifier. Thus, if Matthias wants to call a label "myCoolLabel", the label has to be defined by \label{MaFiMyCoolLabel}.
  • The name of your LaTeX file consists only of your prefix supplemented by the suffix ".tex" (e.g., "MaFi.tex"). Each picture is prefixed with your personal prefix.
  • After the \maketitle call in your LaTeX document, you have to add your abstract with the command "\abstract{ ... }". After the abstract add your local table of contents with the commands "\bigskip\par\hrule\smallskip\par\setcounter{minitocdepth}{2} \dominitoc".
  • We only use the svmult theorem environment. This means, the option "nospthms" and the package "amsthm" can not be used. (The package "amsthm" is not compatible to "svmult".)
  • We do not use the BibTeX compiler to process literature references. Instead of this, you have to add your literature references like presented in the svmult template file "reference.tex". However, you do not use two files but include the references at the end of your thesis file. You have to follow the style given in the template file, i.e., "author, year, title,...".
  • To format the pseudocode of your algorithms you can either use "algorithmicx" together with its floating environment "algorithm" from the package "algorithms", or you can use the "listings" environment. We recommend to start with predefined commands as given by package "algpseudocode". We do not use the package "algorithmic".
  • Your header must look as follows:
    \documentclass{svmult}
    \usepackage[utf8x]{inputenc}
    \usepackage[T1]{fontenc}
    \usepackage{makeidx}
    \usepackage{graphicx}
    \usepackage{multicol}
    \usepackage[bottom]{footmisc}
     \usepackage{amsmath, amssymb, amsfonts, amscd}
    \usepackage{algpseudocode}
    \usepackage{algorithm}
    \usepackage{listings}
    \usepackage{verbatim}
    \makeindex
  • Further packages are not allowed. The page size as defined by svmult is too small for our purposes: Use the following customized svmult file to replace the file shipped with the Springer package: use this file!