Logik in der Informatik
Prof. Dr. Martin Grohe

Institut für Informatik

Mitarbeiterseminar Logik in der Informatik

Freitag, 28. Oktober 2005, 11:15 Uhr
RUD 25, Raum 4.410

Transportation distances under transformations

Panos Giannopoulos
Humboldt-Universität zu Berlin

Over the last few years, transportation distances have been successfully used in measuring the similarity between geometric patterns. In the simplest setting, two patterns are reduced to sets of weighted points in some metric space and then one measures the minimum amount of work needed to transform one set to the other one. In order to measure the similarity independently of transformations one want to find the transformation that minimizes the transportation distance. This results in a quite complex objective function. For example one can ask for the minimum cost (partial) assignment under translations.

We will present simple FPTAS and other approximation schemes for transformations such as translations and rigid motions. We also discuss connections to the Fermat-Weber location problem and open questions on the combinatorial complexity of the objective function.

Zurück zur Vortragsübersicht 

Last modified: Tue Nov 15 11:36:04 CET 2005
André Hernich