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.