講演抄録/キーワード |
講演名 |
2021-10-23 11:10
ポリオミノと格子凸多角形による多層タイル張り ○千田皐汰(電通大)・Erik Demaine・Martin Demaine(マサチューセッツ工科大)・David Eppstein(カリフォルニア大アーバイン校)・Adam Hesterberg(ハーバード大)・堀山貴史(北大)・John Iacono(ブリュッセル自由大)・伊藤大雄(電通大)・Stefan Langerman(ブリュッセル自由大)・上原隆平(北陸先端大)・宇野裕之(阪府大) COMP2021-15 |
抄録 |
(和) |
平面図形の無限個の複製(回転と裏返しを許す)が隙間や重なりの無いように平面を充填するとき,その集合族$¥mathcal{T}$をタイル張りと呼び,$¥mathcal{T}$に属する全ての平面図形が互いに合同であるとき,その平面図形をタイルと呼ぶ.本研究ではこれを拡張した,平面を$k$層の厚さで充填する$k$層タイル張りと,それに属する$k$層タイルを考える.$k$層タイル張りは,簡潔に言えば,平面上の任意の点において平面図形がちょうど$k$回重なるように充填するということを意味する.また,(1層)タイルは任意の正整数$k$に対して自明に$k$層タイルであることから,「タイルではないが,$k(¥geq 2)$層タイルではある」という性質を持つ平面図形が研究対象となる.この性質を持つ平面図形を非自明な$k$層タイルと呼ぶ.本報告では,主にポリオミノと格子凸多角形に着目し,非自明な$k$層タイルに関するいくつかの事実を明らかにする. |
(英) |
A family of plane shapes $¥mathcal{T}$ is called a tiling if they (rotating and reflecting are allowed) cover the whole plane without gaps or overlaps, and if all shapes belonging to $¥mathcal{T}$ are congruent each other, then the shape is called a tile. We study $k$-fold tilings which are extended to cover the plane with $k$ folds and $k$-fold tiles which belong to it. Intuitively it means that a family of plane shapes covers the plane such that they overlap $k$ times at any point in the plane. Since clearly a (1-fold) tile is a $k$-fold tile for any positive integer $k$, the subjects of our research are plane shapes with property "not a tile, but a $k(¥geq 2)$-fold tile." We call a plane shape satisfying this property a nontrivial $k$-fold tile. In this report, we mainly focus on polyominoes and convex lattice polygons and clarify some facts on nontrivial $k$-fold tiles. |
キーワード |
(和) |
多層タイル張り / k層タイル / ポリオミノ / 格子凸多角形 / / / / |
(英) |
multiple tilings / k-fold tiles / polyominoes / convex lattice polygons / / / / |
文献情報 |
信学技報, vol. 121, no. 218, COMP2021-15, pp. 11-18, 2021年10月. |
資料番号 |
COMP2021-15 |
発行日 |
2021-10-16 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2021-15 |