School Seminars and Colloquia

The Computational Geometry of Comparing Shapes

Discrete Structures and Algorithms (Seminar)

by Professor Helmut Alt


Institution: Freie Universitat Berlin
Date: Wed 19th September 2012
Time: 1:00 PM
Location: Old Geology Theatre 2

Abstract: The lecture will be a survey on methods from computational geometry for comparing patterns and shapes that we developed within our work group at Freie Universitaet Berlin. In particular, we will present the ideas and complexity considerations for the computation of two distance measures for shapes, namely the Hausdorff distance and the Frechet distance. Whereas the former is easier to compute, the latter better captures the similarity of shapes as perceived by human observers. Whereas the Frechet distance of curves is efficiently computable, for surfaces it seems computationally intractable and, in fact, is not even known to be computable at all. We will close with some application examples of this theory.