エッシャー風タイリング問題 Escher-style Tiling Problem

与えられた平面図形（左図）になるべく類似したタイル図形を設計する．ただし，タイル図形は隙間なく平面を埋められるものでなくてはならない（右図は左図になるべく類似したタイル図形を敷き詰めた時の図）．このような問題を最適化問題としてうまく定式化（数学的に解くことができる形にする）することが重要となる．さらに定式化した問題を効率的に解くためのアルゴリズムを考案することも重要となる．

The goal is to design a tile shape that closely resembles a given planar figure (left diagram), under the constraint that the tile must be able to tessellate the plane without gaps or overlaps. The resulting tiling (right diagram) should approximate the target figure as closely as possible. This problem should be formulated as an optimization problem—i.e., expressed in a mathematical form that can be solved computationally. Additionally, it is important to develop an efficient algorithm to solve the formulated problem.

Reference:

1. Yuichi Nagata and Shinji Imahori : Escherization with Large Deformations Based on As-Rigid-As-Possible Shape Modeling, ACM Transactions on Graphics, Vol.41, No.2:11, 1-16, 2022. (DOI: 10.1145/3487017)

2. Yuichi Nagata and Shinji Imahori : An Efficient Exhaustive Search Algorithm for the Escherization Problem, Algorithmica, Vol.82, No.9, 2502-2534, 2020. (DOI: 10.1007/s00453-020-00695-6)

3. Yuichi Nagata : Research on automatic generation of artistic paintings called Escher tiling,The 9th international forum on Advanced Technologies (IFAT 2023), Mar. 2023.

4. Yuichi Nagata : Escherization with a Distance Function Focusing on the Similarity of Local Structure, Proceedings of the 15th International Conference on Parallel Problem Solving from Nature (PPSN 2018), LNCS 11101, 108-120, Sep. 2018. (DOI: 10.1007/978-3-319-99253-2_9)

5. 永見 和幹, 永田 裕一 :仮想点を用いたエッシャータイリング問題の改善手法,令和5年度 SICE 四国支部学術講演会, 2023年12月.

6. 居村 亮治, 永田 裕一 :バネモデルを用いた目標図形の自然な変形による エッシャータイリングの生成法, ICE四国支部学術講演会, 2021年12月.    

7. 永田 裕一 :局所的な類似性に着目したエッシャータイリング問題へのアプローチ,電気学会システム研究会, 2021年6月.    

8. 永田 裕一 :一般化距離尺度を用いたエッシャー風タイリング問題の網羅的解法,計算学会進化計算シンポジウム2017, 2017年12月.