OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21110%2F17%3A00316325" target="_blank" >RIV/68407700:21110/17:00316325 - isvavai.cz</a>

Výsledek na webu

<a href="https://ojs.cvut.cz/ojs/index.php/APP/article/view/4651" target="_blank" >https://ojs.cvut.cz/ojs/index.php/APP/article/view/4651</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.14311/APP.2017.13.0135" target="_blank" >10.14311/APP.2017.13.0135</a>

Jazyk výsledku

angličtina

Název v původním jazyce

OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES

Popis výsledku v původním jazyce

Wang tiles proved to be a convenient tool for the design of aperiodic tilings in computer graphics and in materials engineering. While there are several algorithms for generation of finite-sized tilings, they exploit the specific structure of individual tile sets, which prevents their general usage. In this contribution, we reformulate the NP-complete tiling generation problem as a binary linear program, together with its linear and semidefinite relaxations suitable for the branch and bound method. Finally, we assess the performance of the established formulations on generations of several aperiodic tilings reported in the literature, and conclude that the linear relaxation is better suited for the problem.

Název v anglickém jazyce

OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES

Popis výsledku anglicky

Wang tiles proved to be a convenient tool for the design of aperiodic tilings in computer graphics and in materials engineering. While there are several algorithms for generation of finite-sized tilings, they exploit the specific structure of individual tile sets, which prevents their general usage. In this contribution, we reformulate the NP-complete tiling generation problem as a binary linear program, together with its linear and semidefinite relaxations suitable for the branch and bound method. Finally, we assess the performance of the established formulations on generations of several aperiodic tilings reported in the literature, and conclude that the linear relaxation is better suited for the problem.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

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 statě ve sborníku

NMM 2017 - Nano & Macro Mechanics 2017

ISBN

978-80-01-06346-0

ISSN

2336-5382

e-ISSN

—

Počet stran výsledku

7

Strana od-do

135-141

Název nakladatele

Czech Technical University in Prague

Místo vydání

Praha

Místo konání akce

Praha

Datum konání akce

21. 9. 2017

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—