Geometric Point Pattern Matching in the Knuth-Morris-Pratt Way
Esko Ukkonen · Zenodo (CERN European Organization for Nuclear Research) · 2020
Abstract: Given finite sets P and T of points in the Euclidean space R d,thepoint pattern matching problem studied in this paper is to find all translations f ∈ R d 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 |) wherer 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 ∈ R d and positive integers m1,...,mr arepresentationP = {p + i1e1 + ···+ irer | 0 ≤ ij ≤ mj} where the ij’s are integers. Both P and T are given to the search algorithm in the lexicographic order.