Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2022.23
URN: urn:nbn:de:0030-drops-161508
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16150/
Radoszewski, Jakub ; Rytter, Wojciech ; Straszyński, Juliusz ; Waleń, Tomasz ; Zuba, Wiktor
Rectangular Tile Covers of 2D-Strings
| pdf-format: |
|
Abstract
We consider tile covers of 2D-strings which are a generalization of periodicity of 1D-strings. We say that a 2D-string A is a tile cover of a 2D-string S if S can be decomposed into non-overlapping 2D-strings, each of them equal to A or to A^T, where A^T is the transpose of A. We show that all tile covers of a 2D-string of size N can be computed in 𝒪(N^{1+ε}) time for any ε > 0. We also show a linear-time algorithm for computing all 1D-strings being tile covers of a 2D-string.
BibTeX - Entry
@InProceedings{radoszewski_et_al:LIPIcs.CPM.2022.23,
author = {Radoszewski, Jakub and Rytter, Wojciech and Straszy\'{n}ski, Juliusz and Wale\'{n}, Tomasz and Zuba, Wiktor},
title = {{Rectangular Tile Covers of 2D-Strings}},
booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
pages = {23:1--23:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-234-1},
ISSN = {1868-8969},
year = {2022},
volume = {223},
editor = {Bannai, Hideo and Holub, Jan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16150},
URN = {urn:nbn:de:0030-drops-161508},
doi = {10.4230/LIPIcs.CPM.2022.23},
annote = {Keywords: tile cover, periodicity, efficient algorithm}
}
| Keywords: | tile cover, periodicity, efficient algorithm | |
| Seminar: | 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 22.06.2022 |
