Dynamic and approximate pattern matching in 2D

We consider dynamic and online variants of 2D pattern matching between an mXm pattern and an nXn text. All the algorithms we give are randomised and give correct outputs with at least constant probability. - For dynamic 2D exact matching where updates change individual symbols in the text, we show updates can be performed in O(log2 n) time and queries in O(log2 m) time. - We then consider a model where an update is a new 2D pattern and a query is a location in the text.

For this setting we show that Hamming distance queries can be answered in O(log m + H) time, where H is the relevant Hamming distance. - Extending this work to allow approximation, we give an efficient algorithm which returns a (1+ε) approximation of the Hamming distance at a given location in O(ε−2 log2 m log log n) time.

Finally, we consider a different setting inspired by previous work on locality sensitive hashing (LSH). Given a threshold k and after building the 2D text index and receiving a 2D query pattern, we must output a location where the Hamming distance is at most (1 + ε)k as long as there exists a location where the Hamming distance is at most k. - For our LSH inspired 2D indexing problem, the text can be preprocessed in O(n2(4/3+1/(1+ε)) log3 n) time into a data structure of size O(n2(1+1/(1+ε))) with query time O(n2(1/(1+ε))m2).