查看文章

This paper presents simple and deterministic algorithms for partial point set pattern matching in 2D. Given a set P of n points, called sample set, and a query set Q of k points (n⩾k), the problem is to find a matching of Q with a subset of P under rigid motion. The match may be of two types: exact and approximate. If an exact matching exists, then each point in Q coincides with the corresponding point in P under some translation and/or rotation. For an approximate match, some translation and/or rotation may be allowed such that each point in Q lies in a predefined ε-neighborhood region around some point in P. The proposed algorithm for the exact matching needs O(n²) space and O(n²logn) preprocessing time. The existence of a match for a given query set Q can be checked in O(kαlogn) time in the worst-case, where α is the maximum number of equidistant pairs of point in P. For a set of n points, α may be O(n^4/3) in …