Abstract: We will survey recent works on the topic and present new results.
Our results involve both theoretic and practical aspects of the problem.
Given two pointsets in d-dimensional space, some delta > 0, and a group G of
transformations, the problems we consider are: 1) Pattern Matching (PM) -
find T in G if exists, such that h(T(P),Q) < delta, where h(.,.) is
the directional Hausdorff distance, 2) Minimum Hausdorff Distance (MHD) -
find the smallest delta such that such T exists, and 3) Largest
Common Pointset (LCP) - find the largest subset, B of P, and a transformation T,
such that such h(T(B),Q) < delta exists, and return T and B. We consider
approximation, randomized algorithms and practical input sensitive approaches
for various groups of transformations in the plane and in any fixed d.

Joint work with Klara Kedem