Matching points into pairwise-disjoint noise regions: combinatorial bounds and algorithms

We consider several cases of the point matching problem in which we are to find a transformation of a set of n points such that each transformed point lies in one of n given pairwise-disjoint 'noise regions.' We prove upper and lower bounds on the number of possible matches, under a variety of types of transformations (rotations, translations, similarity) and noise regions (circles, squares, polygons). We also give efficient algorithms for computing the set of all possible matches, along with a corresponding transformation that realizes each match.