Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane. P and Q, and some (arbitrary) delta > 0, find a similarity transformation T (translation, rotation and scale) such that h(T(P), Q) < delta, where h(.,.) is the directional Hausdorff distance with L-infinity as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, delta is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L-infinity distance between every pair of points in Q is at least 8 delta, then the problem can be solved in O(mn(2) logn) time, where m and n are the numbers of points in P and Q respectively. If the L-infinity distance between every pair of points in Q is at least c delta, for some c, 0 < c < 1, we present a randomized approximate solution with expected runtime O(n(2)c(-4)epsilon(-8)log(4) mn), where epsilon > 0 controls the approximation. Our approximation is on the size of the subset, B subset of P, such that h(T(B), Q) < delta and vertical bar B vertical bar > (1 - epsilon) vertical bar P vertical bar with high probability. (C) 2009 Elsevier B.V. All rights reserved.