A Simple Algorithm for Approximate Partial Point Set Pattern Matching under Rigid Motion.

This paper deals with the problem of approximate point set pattern matching in 2D. Given a set P of n points, called sample set, and a query setQ of k points (k ≤ n), the problem is to find a match of Q with a subset of P under rigid motion (rotation and/or translation) transformation such that each point in Q lies in the ε-neighborhood of a point in P. The ε-neighborhood region of a point p_i ϵ P is an axis-parallel square having each side of length ε and p_i at its centroid. We assume that the point set is well-seperated in the sense that for a given ε> 0, each pair of points p, p' ϵ P satisfy at least one of the following two conditions (i) |x(p) − x(p')| ≥ ε, and (ii) |y(p) − y(p')| ≥ 3ε, and we propose an algorithm for the approximate matching that can find a match (if it exists) under rigid motion in O(n²k²(klogk + logn)) time. If only translation is considered then the existence of a match can be tested in O(nk² logn) time. The salient feature of our algorithm for the rigid motion and translation is that it avoids the use of intersection of high degree curves. [ABSTRACT FROM AUTHOR]