Matching Points into Pairwise-Disjoint Noise Regions: Combinatorial Bounds and Algorithms

Abstract
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.

This publication has 0 references indexed in Scilit: