Low Distortion Maps between Point Sets
Yuval Rabani, Technion and Cornell University
March 5, 2004

Abstract

We initiate the study of the {\em minimum distortion} problem: given as input two $n$-point metric spaces, find a bijection between them with minimum distortion.
This is an abstraction of certain geometric problems in shape and image matching, and is also a natural variation and extension of the fundamental problems of graph isomorphism and bandwidth. Our focus is on algorithms that find an optimal (or near-optimal) bijection when the distortion is fairly small. We present a polynomial time algorithm that finds an optimal bijection between two line metrics, provided the distortion is at most $2+\sqrt{5}$. We also give a parameterized polynomial time algorithm that finds an optimal bijection between an arbitrary unweighted graph metric and a bounded-degree tree metric.

This is joint work with Claire Kenyon and Alistair Sinclair.