Two-Dimensional Maximal Repetitions

Abstract Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition . We provide initial bounds on the number of maximal 2D repetitions that can occur in an n × n array. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions. The algorithm is efficient and straightforward, with runtime O ( n 2 log ⁡ n + ρ ) , where n 2 is the size of the input array and ρ is the number of maximal 2D repetitions in the output.