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.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.