In many applications in computer graphics, computer vision, pattern recognition, or other related fields, shape matching plays a key role. In this thesis we consider several shape matching problems and give algorithms to solve them.

First, we introduce an approximate version of the largest common point set problem. The largest common point set problem is a standard problem in pattern matching. For two given point sets, we want to find a transformation that matches maximum subsets of the two point sets under a certain metric. Our algorithm works in the plane and we assume that point sets move under translations.

Second, we present an approximation algorithm to return a rigid motion of three-dimensional Euclidean space for two given convex polyhedra such that the volume of the overlap of...[ Read more ]

In many applications in computer graphics, computer vision, pattern recognition, or other related fields, shape matching plays a key role. In this thesis we consider several shape matching problems and give algorithms to solve them.

First, we introduce an approximate version of the largest common point set problem. The largest common point set problem is a standard problem in pattern matching. For two given point sets, we want to find a transformation that matches maximum subsets of the two point sets under a certain metric. Our algorithm works in the plane and we assume that point sets move under translations.

Second, we present an approximation algorithm to return a rigid motion of three-dimensional Euclidean space for two given convex polyhedra such that the volume of the overlap of the polyhedra is maximized. We apply an existing algorithm for translations for many sampled candidate rotations. The challenge is to deal with three-dimensional rotations.

Last, we explore convex polytope matching problem with respect to the volume of the symmetric difference metric. We prove that the function of the volume of the symmetric difference is convex and therefore we can apply convex programming to our problem. We give necessary and sufficient conditions for local minima of the function.