2026-07-23T16:36:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13963 2024-03-06T10:53:00Z ddc:004 open_access

Computing Covers of 2D-Strings Charalampopoulos, Panagiotis Radoszewski, Jakub Rytter, Wojciech Waleń, Tomasz Zuba, Wiktor 2D-string cover dynamic Klee’s measure problem We consider two notions of covers of a two-dimensional string T. A (rectangular) subarray P of T is a 2D-cover of T if each position of T is in an occurrence of P in T. A one-dimensional string S is a 1D-cover of T if its vertical and horizontal occurrences in T cover all positions of T. We show how to compute the smallest-area 2D-cover of an m × n array T in the optimal 𝒪(N) time, where N = mn, all aperiodic 2D-covers of T in 𝒪(N log N) time, and all 2D-covers of T in N^{4/3}⋅ log^{𝒪(1)}N time. Further, we show how to compute all 1D-covers in the optimal 𝒪(N) time. Along the way, we show that the Klee’s measure of a set of rectangles, each of width and height at least √n, on an n × n grid can be maintained in √n⋅ log^{𝒪(1)}n time per insertion or deletion of a rectangle, a result which could be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Panagiotis Charalampopoulos and Jakub Radoszewski and Wojciech Rytter and Tomasz Waleń and Wiktor Zuba 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.12 urn:nbn:de:0030-drops-139635 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.12 eng https://creativecommons.org/licenses/by/4.0/legalcode