###
Exact and Approximate Two Dimensional Pattern Matching allowing Rotations

####
Kimmo Fredriksson, Gonzalo Navarro and Esko Ukkonen

We give fast filtering algorithms for searching a 2-dimensional
pattern in a 2-dimensional text allowing any rotation of the pattern.
We consider the cases of exact and approximate matching under several
matching models, improving the previous results. For a text of size *n x
n* character and a pattern of size *m x m* characters, the
exact matching takes average time *O(n^2/m)*. If we allow
*k*-mismatches of characters, then our best algorithm achieves *O(n^2
sqrt(k)/m)* average time, for reasonable error levels. For large *k*,
we obtain a *O(n^2 k^(3/2) sqrt(log m)/m)* average time algorithm.
We generalize the algorithms for the matching model where the sum of
absolute differences between characters is at most *k*.