###
An Index for Two Dimensional String Matching Allowing Rotations

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

We present an index to search a two-dimensional pattern of size *m x m*
in a two-dimensional text of size *n x n*, even when the pattern appears
rotated in the text. The index is based on (path compressed) tries. By using
*O(n^2)* (i.e. linear) space the index can search the pattern in
*O((log_sigma(n))^(5/2))* time on average, where *sigma* is the alphabet
size. We also consider various schemes for approximate matching,
for which we obtain
either *O(polylog_sigma(n))* or *O(n^(2*lambda))* search time, where
*lambda < 1* in most useful cases. A larger index of size
*O(n^2(log_sigma(n))^(3/2))* yields an average time of *O(log_sigma(n))*
for the simplest matching model. The algorithms have
applications e.g. in content based information retrieval from image databases.