Design and Analysis of Application-Oriented Geometric Algorithms


Prof. Dr. Helmut Alt; Freie Universität Berlin

Prof. Dr. Christian Knauer; Universität Bayreuth


Project website


The goal of this project is to close a gap between theoretically designed and studied algorithms and the methods that are widely used in practice, especially heuristics. We consider primarily but not exclusively the problem of the geometric shape matching. There are many algorithms and heuristic methods that work well and are widely used in practice but lack theoretical analysis. We analyze some of such heuristics with respect to the following questions:

  1. What is computed by the method? The quality of the computed results is often not known or even not clearly defined.
  2. What is the running time of the method? In many cases there is a certain trade-off between the running time and the quality of results.

It might be necessary to constraint the inputs of the methods and to characterize the cases that occur in practice in order to be able to perform the analysis. Besides these theoretical studies we also plan to do prototype implementations of the designed algorithms to verify their practicability. The research focuses on the following problems:

  • Patterns and shapes
    • Probabilistic shape matching
    • Symmetry detection
    • Application oriented methods
  • Packing and stacking geometric objects
  • Realistic input models
    • Geometric shape matching
    • Geometric search structures
  • Principal component analysis

[ Back ]