Bounded Wang tilings with integer programming and graph-based heuristics

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21110/23:00366111

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Bounded Wang tilings with integer programming and graph-based heuristics

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Bounded Wang tilings with integer programming and graph-based heuristics

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10102 - Applied mathematics

Projekt

<a href="/cs/project/GX19-26143X" target="_blank" >GX19-26143X: Neperiodické materiály vykazující strukturované deformace: Modulární návrh a výroba</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Scientific Reports

ISSN

2045-2322

e-ISSN

2045-2322

Svazek periodika

13

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

4865

Kód UT WoS článku

001027998000026

EID výsledku v databázi Scopus

2-s2.0-85151044921