Logik in der Informatik Prof. Dr. Martin Grohe

Institut für Informatik

Transportation distances under transformations

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.