Entwurf und Analyse anwendungsbezogener geometrischer Algorithmen

• Applicant: Professor Dr. Helmut Alt
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 47980957

The research proposed here is a continuation of an ongoing project considering heuristic methods for geometric problems. In particular, we investigate such methods for shape and pattern matching and for geometric optimization problems, such as area-efficient stacking and packing of geometric objects. On the one hand we plan to develop such methods, implement them, and determine their performance experimentally. On the other hand, however, a major objective of our research is to theoretically analyze these heuristics and already existing ones in order to be able to explain their performance. Part of this analysis is the consideration and characterization of realistic inputs for which the algorithms work well although there are possibly constructed examples where they show inefficient worst case performance.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering
• Participating Person: Professor Dr. Christian Knauer