Entwurf und Analyse anwendungsbezogener geometrischer Algorithmen

点击翻译按钮获取中文摘要

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.