2026-07-24T18:02:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20120 2024-06-18T13:20:58Z ddc:004 open_access

Searching 2D-Strings for Matching Frames Boneh, Itai Fried, Dvir Golan, Shay Kraus, Matan Miclăuş, Adrian Shur, Arseny 2D string matching frame LCP multidimensional range query We study a natural type of repetitions in 2-dimensional strings. Such a repetition, called a matching frame, is a rectangular substring of size at least 2× 2 with equal marginal rows and equal marginal columns. Matching frames first appeared in literature in the context of Wang tiles. We present two algorithms finding a matching frame with the maximum perimeter in a given n× m input string. The first algorithm solves the problem exactly in Õ(n^{2.5}) time (assuming n ≥ m). The second algorithm finds a (1-ε)-approximate solution in Õ((nm)/ε⁴) time, which is near linear in the size of the input for constant ε. In particular, by setting ε = O(1) the second algorithm decides the existence of a matching frame in a given string in Õ(nm) time. Some technical elements and structural properties used in these algorithms can be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Itai Boneh and Dvir Fried and Shay Golan and Matan Kraus and Adrian Miclăuş and Arseny Shur 2024 Is Part Of LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2024.10 urn:nbn:de:0030-drops-201205 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.10 eng https://creativecommons.org/licenses/by/4.0/legalcode