License: 
Creative Commons Attribution 4.0 International 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16150/
Radoszewski, Jakub ;
Rytter, Wojciech ;
Straszyński, Juliusz ;
Waleń, Tomasz ;
Zuba, Wiktor
Rectangular Tile Covers of 2D-Strings
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 |
|
Collection: |
|
33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.06.2022 |
