講演抄録/キーワード |
講演名 |
2014-06-14 13:55
pmg タイリング可能なポリオミノの列挙 ○西岡 潤・堀山貴史(埼玉大) COMP2014-14 |
抄録 |
(和) |
ポリオミノは単位正方形を辺同士が接続するように組み合わせてできる図形である.pmg タイリングは,鏡映とすべり鏡映の繰り返しで,基本図形を平面に隙間なく重なりなく敷き詰めるタイリングである.本稿では,pmgタイリング可能なポリオミノの列挙アルゴリズムを提案する.提案手法は,列挙対象が内包する木構造を利用して列挙を行う逆探索に基づいており,ルールにより次に出力する図形を求める.このため,過去の生成図形との同一性判定を必要とする試行錯誤による従来法に対して,計算時間の効率化と計算領域の削減が図れる.また,本稿では,逆探索に基づく p4 (90 度回転) タイリングでの証明を拡張し,pmg 特有の証明を加えることで,pmg タイリング可能な図形を漏れなく重複なく列挙できることを示す. |
(英) |
Polyominoes are the two dimensional shapes made by connecting n equal-sized squares, joined along their edges. In this paper, we propose algorithms to enumerate all polyominoes for pmg tiling, i.e., those covering the plane by reflection and glide reflection. Our approach is based on the reverse search, in which we design rules to generate the next. By this approach, appart from the conventional method with trial and error, we can reduce the computational time and also the space complexity. The proof of the enumeration in this paper is based on that for p4 tiling (i.e., tiling by 4-fold rotations). Since new situations arise for pmg tiling, the proof is extended to meet with them.
(This article is a technical report without peer review.) |
キーワード |
(和) |
列挙アルゴリズム / 逆探索 / タイリング / / / / / |
(英) |
Enumeration algorithm / reverse search / tiling / / / / / |
文献情報 |
信学技報, vol. 114, no. 80, COMP2014-14, pp. 107-114, 2014年6月. |
資料番号 |
COMP2014-14 |
発行日 |
2014-06-06 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2014-14 |