Computer Sciences Seminar
Thursday, April 4
12:30 PM, NAC 8/206

Algorithmic Problems in Point Pattern Matching

Peter Brass
Free University Berlin

Abstract
Geometric pattern matching is an important subject that, depending on the model of patterns and geometric objects, can lead to quite diverse problems. In this talk I will discuss some algorithmic aspects of the point pattern model, where the objects and patterns are finite point sets. This model is especially suited for the use of methods of computational geometry. The general question `Does pattern A occur in the background B' then becomes, e.g., `Does the set B contain a subset congruent to A?'. I will discuss this and related problems, and present results on several exact, approximate, and preprocessing variants.

Bio
Peter Brass received his M.S. in mathematics and computer science in 1990 and his Ph.D. in 1992, both from the Technical University of Braunschweig, Germany. Since then he had positions as a Postdoc and Research Associate at the University of Greifswald and the Free University of Berlin, and currently holds a DFG Heisenberg-fellowship, which he spends at the Theoretical Computer Science Group of the Free University. His research interest are algorithms, especially in computational geometry, and the underlying mathematical problems.