摘要：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 ⊆ 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 e 1, ... , er ∈ Rd and positive integers m 1, ... , mr a representation P = { p + i 1 e 1 + ⋅⋅⋅ + irer | 0 ≤ ij ≤ mj } where the ij 's are integers. Both P and T are given to the search algorithm in the lexicographic order.
关键词：Knuth-Morris-Pratt algorithm, pattern matching, point sets, translation
