The Computational Geometry of Comparing Shapes
by Professor Helmut Alt
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.