Determining the similarity between objects is a fundamental problem in computer vision and pattern recognition, but also in other fields of computer science. This thesis concentrates on the matching problem, which has received a lot of attention in Computational Geometry.

Given a class of shapes S, a set of transformations T, mapping shapes onto shapes, and a distance measure d on S, the matching problem with respect to S, T, and d is defined as follows: Given two shapes A, B in S, compute a transformation t* in T that minimizes d(t*(A),B).

We consider solid shapes, i.e., full-dimensional shapes, in arbitrary dimension and assume that they are given by an oracle that generates uniformly distributed random points from the shapes. This is a very rich class of shapes that contains the class of finite unions of simplices as a subclass. We study matching under translations and rigid motions (translation and rotation). Throughout this work, the volume of the symmetric difference is used as distance measure for the matching problem. Maximizing the volume of the overlap is equivalent to minimizing the volume of the symmetric difference under translations and rigid motions.

We study a probabilistic approach to the shape matching problem. The main idea is quite simple. Given two shapes A and B, repeat the following random experiment very often: Select random point samples of appropriate size from each shape and compute a transformation that maps the point sample of one shape to the sample of the other shape. Store this transformation. In each step, we extend the collection of random transformations by one. Clusters in the transformation space indicate transformations that map large parts of the shapes onto each other. We determine a densest cluster and output its center.

This thesis describes probabilistic algorithms for matching solid shapes in arbitrary dimension under translations and rigid motions. The algorithms are a priori heuristics. The main focus is on analyzing them and on proving that they maximize the volume of overlap approximately by solving the following instance of the matching problem. Given two solid shapes A and B, an error tolerance eps in (0,1), and an allowed probability of failure p in (0,1), the problem is to compute a transformation t* such that with probability at least 1-p, we have that the volume of the intersection of t*(A) and B is at least as large as the volume of the intersection of t(A) and B minus an error of e times the volume of A for all transformations t, in particular for transformations maximizing the volume of overlap.

The approach is mainly of theoretical interest. Still, the algorithms are so simple that they can easily be implemented, which we show by giving experimental results of a test implementation for 2-dimensional shapes.