Sequential and Indexed Two-Dimensional Combinatorial Template Matching
Kimmo Fredriksson, Gonzalo Navarro, and Esko Ukkonen
We present new and faster algorithms to search for a 2-dimensional
pattern in a 2-dimensional text allowing any rotation of the pattern.
This has applications such as image databases and computational biology.
We consider the cases of exact and approximate matching under several
matching models, using a combinatorial approach that generalizes
string matching techniques. We focus on sequential
algorithms, where only the pattern can be preprocessed, as well as on indexed
algorithms, where the text is preprocessed and an index built on it.
On sequential searching we derive average-case lower bounds and then
obtain optimal average-case algorithms for all the matching models. At the
same time, these algorithms are worst-case optimal. On indexed searching we
obtain search time polylogarithmic on the text size, as well as sublinear time
in general for approximate searching.