Bounded Wang tilings with integer programming and graph-based heuristics
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F23%3A00575483" target="_blank" >RIV/67985556:_____/23:00575483 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21110/23:00366111
Result on the web
<a href="https://www.nature.com/articles/s41598-023-31786-3" target="_blank" >https://www.nature.com/articles/s41598-023-31786-3</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1038/s41598-023-31786-3" target="_blank" >10.1038/s41598-023-31786-3</a>
Alternative languages
Result language
angličtina
Original language name
Bounded Wang tilings with integer programming and graph-based heuristics
Original language description
Wang tiles enable efficient pattern compression while avoiding the periodicity in tile distribution via programmable matching rules. However, most research in Wang tilings has considered tiling the infinite plane. Motivated by emerging applications in materials engineering, we consider the bounded version of the tiling problem and offer four integer programming formulations to construct valid or nearly-valid Wang tilings: a decision, maximum-rectangular tiling, maximum cover, and maximum adjacency constraint satisfaction formulations. To facilitate a finer control over the resulting tilings, we extend these programs with tile-based, color-based, packing, and variable-sized periodic constraints. Furthermore, we introduce an efficient heuristic algorithm for the maximum-cover variant based on the shortest path search in directed acyclic graphs and derive simple modifications to provide a 1/2 approximation guarantee for arbitrary tile sets, and a 2/3 guarantee for tile sets with cyclic transducers. Finally, we benchmark the performance of the integer programming formulations and of the heuristic algorithms showing that the heuristics provide very competitive outputs in a fraction of time. As a by-product, we reveal errors in two well-known aperiodic tile sets: the Knuth tile set contains a tile unusable in two-way infinite tilings, and the Lagae corner tile set is not aperiodic.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10102 - Applied mathematics
Result continuities
Project
<a href="/en/project/GX19-26143X" target="_blank" >GX19-26143X: Non-periodic pattern-forming metamaterials: Modular design and fabrication</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Scientific Reports
ISSN
2045-2322
e-ISSN
2045-2322
Volume of the periodical
13
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
22
Pages from-to
4865
UT code for WoS article
001027998000026
EID of the result in the Scopus database
2-s2.0-85151044921