Shape matching is an important topic in computational geometry, 
computer vision, image retrieval, object recognition and robotics. For a fixed 
distance measure D and a class of transformations T we can describe the 
problem as follows: Given two shapes A and B in R^d, find a 
transformation T^* in T, such that the distance between A and T^*(B) is 
minimal among all transformations in T. Usually finding such a transformation 
is computationally expensive, if at all possible. Thus we concentrate on 
approximation algorithms. We follow an approach by Alt, Behrends and Blömer, 
and Alt, Aichholzer and Rote. They use mappings called reference points to fix 
the relative position between the two sets. A reference point is a 
Lipschitz continuous mapping from the set of shapes into R^d which is 
equivariant under the considered class of transformations.
This approach reduces the degrees of freedom of the underlying problem
by the dimension d.

In this thesis we study approximation algorithms for shape matching
with respect to various metrics, e.g., the Hausdorff distance, the
Earth Mover's Distance, the Monge-Kantorovich Distance and the
bottleneck distance. We investigate translations, rigid motions,
i.e., combinations of translations and rotations, and similarities,
i.e., combinations of rigid motions and scalings.

The basic structure of the approximation algorithms is the same for all
metrics and we describe our approach in an abstract reference point
framework. We first determine the relative position of the two shapes
to each other by computing their reference points. We then translate
the shapes such that the reference points coincide. Next we
determine a rotation for one of the shapes such that the distance of
the two shapes is at most a constant times
their optimal distance. Similarities can always
be dealt with by finding an approximate scaling before finding the
rotation.