OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES
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....
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Czech Technical University in Prague
2017-11-01
|
| Series: | Acta Polytechnica CTU Proceedings |
| Subjects: | |
| Online Access: | https://ojs.cvut.cz/ojs/index.php/APP/article/view/4651 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849709493317795840 |
|---|---|
| author | Marek Tyburec Jan Zeman |
| author_facet | Marek Tyburec Jan Zeman |
| author_sort | Marek Tyburec |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-1bd425fc276a4791802122dae8c337db |
| institution | DOAJ |
| issn | 2336-5382 |
| language | English |
| publishDate | 2017-11-01 |
| publisher | Czech Technical University in Prague |
| record_format | Article |
| series | Acta Polytechnica CTU Proceedings |
| spelling | doaj-art-1bd425fc276a4791802122dae8c337db2025-08-20T03:15:16ZengCzech Technical University in PragueActa Polytechnica CTU Proceedings2336-53822017-11-0113013514110.14311/APP.2017.13.01354017OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILESMarek Tyburec0Jan Zeman1Czech Technical University in Prague, Faculty of Civil Engineering, Department of Mechanics, Thákurova 7, 166 29 Prague 6, Czech RepublicCzech Technical University in Prague, Faculty of Civil Engineering, Department of Mechanics, Thákurova 7, 166 29 Prague 6, Czech RepublicWang 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.https://ojs.cvut.cz/ojs/index.php/APP/article/view/4651Wang tiles, binary and continuous linear programming, semidefinite programming, |
| spellingShingle | Marek Tyburec Jan Zeman OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES Acta Polytechnica CTU Proceedings Wang tiles, binary and continuous linear programming, semidefinite programming, |
| title | OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES |
| title_full | OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES |
| title_fullStr | OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES |
| title_full_unstemmed | OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES |
| title_short | OPTIMIZATION-BASED APPROACH TO TILING OF FINITE AREAS WITH ARBITRARY SETS OF WANG TILES |
| title_sort | optimization based approach to tiling of finite areas with arbitrary sets of wang tiles |
| topic | Wang tiles, binary and continuous linear programming, semidefinite programming, |
| url | https://ojs.cvut.cz/ojs/index.php/APP/article/view/4651 |
| work_keys_str_mv | AT marektyburec optimizationbasedapproachtotilingoffiniteareaswitharbitrarysetsofwangtiles AT janzeman optimizationbasedapproachtotilingoffiniteareaswitharbitrarysetsofwangtiles |