Geometric Point Pattern Matching in the Knuth–Morris–Pratt Way

Abstract: Given finite sets P and T of points in the Euclidean space Rd,the point pattern matching problem studied in this paper is to find all translations f Є Rd such that P + f (subset of) T. A fast search algorithm with some variants is presented for point patterns P that have regular grid.like geometric shape. The algorithm is analogous to the Knuth.Morris.Pratt algorithm of string matching. The time requirement of the search is O(r|T|)where r is the grid dimension of P. Pattern P has grid dimension r = 1 if it consists of evenly spaced points on a line. In general, a pattern P is an r.dimensional grid if it has for some p Є P and e1,...,er Є Rd and positive integers m1,...,mr arepresentation P = {p+ i1e1 + .....+ ir er |0≤ij ≤mj } where the ij s are integers. Both P and T are given to the search algorithm in the lexicographic order.