# 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.