Algorithms for point set matching with k-differences
The largest common point set problem (LCP) is, given two point set P and Q in d-dimensional Euclidean space, to find a subset of P with the maximum cardinality that is congruent to some subset of Q. We consider a special case of LCP in which the size of the largest common point set is at least (vertical bar P vertical bar + vertical bar Q vertical bar - k)/2. We develop efficient algorithms for this special case of LCP and a related problem. In particular, we present an O (k(3)n(1.34) + kn(2) log n) time algorithm for LCP in two-dimensions, which is much better for small k than an existing 0 (n(3.2) log n) time algorithm, where n max {vertical bar P vertical bar,vertical bar Q vertical bar}.
point set matching largest common point set approximate string matching computational geometry congruence pattern matching