Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 16 / Issue 14

available in:   PDF (127 kB) PS (125 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-016-14-1902


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

Esko Ukkonen (University of Helsinki, Finland)

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 fRd such that P + fT. 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 pP and e1, ... , erRd and positive integers m1, ... , mr a representation P = {p + i1e1 + ⋅⋅⋅ + irer | 0 ≤ ijmj} where the ij's are integers. Both P and T are given to the search algorithm in the lexicographic order.

Keywords: Knuth-Morris-Pratt algorithm, pattern matching, point sets, translation,

Categories: F.2, I.3, I.7