Optimal discovery of repetitions in 2D

Repetitive substructures in two-dimensional arrays emerge in speeding up searches and have been recently studied also independently in an attempt to parallel some of the classical derivations concerning repetitions in strings. The present paper focuses on repetitions in two dimensions that manifest themselves in form of two “tandem” occurrences of a same primitive rectangular pattern W where the two replicas touch each other with either one side or corner. Being primitive here means that W cannot be expressed in turn by repeated tiling of another array. The main result of the paper is an O(n3logn) algorithm for detecting all “side-sharing” repetitions in an n×n array. This is optimal, based on bounds on the number of such repetitions established in previous work. With easy adaptations, these constructions lead to an equally optimal, O(n4) algorithm for repetitions of the second type.