Exact and approximate Geometric Pattern Matching for point sets in the plane under similarity transformations
Dror Aiger, Klara Kedem · 2007
We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some � > 0, find a similarity transformation (translation, rotation and scale) such that h(T(P),Q) < �, where h(.,.) is the directional Hausdorff distance with L1 as the underlying metric. Similarity transformations have not been dealt with in the context of the directional Hausdorff distance and we fill the gap here. We present efficient, exact and approximate algorithms for this problem imposing a reasonable separation restriction on the set Q. For the exact case if the minimum L1 distance between every pair of points in Q is 8� then the problem can be solved in O(n 2 mlogn) time where m and n are the number of points in P and Q respectively.