Computational Geometry / 計算幾何学

Hiroshi FUKUDA

(Since 1994)

一般化ゴスパー曲線 / Generalized Gosper space filling curves

(クリックすると再帰が進みます)
右の図形はゴスパーの怪物曲線を一般化して,発見した13本の線分から成る一般化ゴスパー曲線のジェネレーターです。13本の線分の1本1本を13本の線分全体を1/13に縮小したものに置き換える操作を繰り返すと,平面をべったり敷き詰めるフラクタル次元2の一般化ゴスパー曲線が得られます。図形の上でマウスをクリックすると再帰が進み,右クリックすると戻ります。我々は,このような一般化ゴスパー曲線が無数に存在することを示しました。

一般化ゴスパー曲線は,黒丸から白丸へ至る折れ線で,その折れ線は 1) 途中で交差しない一筆書きで, 2) 線分を辺とする三角格子の全頂点を通る という性質を持っています。 この美しい性質が怪物曲線と呼ばれる所以ですが,美しいばかりでなく平面アンテナへの応用なども試みられています。

Spence T G, Werner D H 2011 Generalized Space-Filling Gosper Curves and Their Application to the Design of Wideband Modular Planar Antenna Arrays IEEE Transactions on Antennas and Propagation 58(12):3931 - 3941
ジェネレーターの線分の本数を次数と呼びます。次数7がゴスパーの怪物曲線です。文献4に次数37までの全ての図が掲載されています。

未解決問題:一般化ゴスパー曲線の次数はn=6k+1, k=1,2,3,...に限られるという予想を証明して下さい。

  1. 福田 宏, 中村 義作 2010 「ゴスパー曲線とその一般化」 『離散数学のすすめ』伊藤 大雄, 宇野 裕之/編著 第11章 pp.152-167 (現代数学社 2010年5月15日初版1刷)
  2. 福田 宏, 中村 義作 2008 「ゴスパー曲線とその一般化」 『理系への数学』第41巻第6号通巻498号 離散数学のすすめ15 pp.55-60 (現代数学社)
  3. Akiyama J, Fukuda H, Ito H, Nakamura G 2007 Infinite Series of Generalized Gosper Space Filling Curves Discrete Geometry, Combinatorics and Graph Theory. CJCDGCGT 2005. Lecture Notes in Computer Science 4381 1-9 DOI:10.1007/978-3-540-70666-3
  4. Fukuda H, Shimizu M, Nakamura G 2001 New Gosper Space Filling Curves Proceedings of the International Conference on Computer Graphics and Imaging, CGIM2001 34-38 reprint

ポリオミノとポリイアモンドのアイソヘドラルタイリング / Isohedral tilings of polyominoes and polyiamonds


(a)

(b)
図1

(a)

(b)
図2

(a)

(b)
図3
まず,用語です。

図1(b)はポリオミノによるpgアイソヘドラルタイリングの応用として,我々の提案したpgパータイリング図形です。図1(a)の9-オミノはpg対称性をもつアイソヘドラルタイリングが可能で,図1(b)の完全タイルは,図1(a)の9-オミノを構成する9つの正方形を9-オミノで置換するという再帰的操作を繰り返して得られます。ポリオミノを構成する正方形がポリオミノに置換されるので,この方法で収束する図形はパータイルです。このパータイルを拡大したタイリングは,元のタイリングの対称性pgを持つ,いわばpgパータイリングです。福田のホームページの背景はこのpgパータイリングです。詳しくは文献1と7参照。

  1. 福田 宏, 中村 義作 2013 『エッシャーの絵から結晶構造へ(増補版)』 (海鳴社バウンダリー叢書,2013年4月25日第1刷発行) ISBN978-4-87525-296-2
  2. 福田 宏 2008 科学研究費補助金 基盤研究C 数学一般(含確率論・統計数学)「ポリオミノとポリイアモンドを用いたアイソヘドラルタイリングの研究
  3. Fukuda H, Kanomata C, Mutoh N, Nakamura G, Schattschneider D 2011 Polyominoes and Polyiamonds as Fundamental Domains of Isohedral Tilings with Rotational Symmetry Symmetry 3(4) 828-851 doi:10.3390/sym3040828 arXiv:1007.2460.
  4. Fukuda H, Kanomata C, Mutoh N, Nakamura G, Schattschneider D 2011 Polyominoes and Polyiamonds as Fundamental Domains for Isohedral Tilings of Crystal Class D2 Symmetry 3(2) 325-364 doi:10.3390/sym3020325
  5. Fukuda H, Mutoh N, Nakamura G, Schattschneider S 2008 Enumeration of Polyominoes, Polyiamonds and Polyhexes for Isohedral Tilings with Rotational Symmetry Computational Geometry and Graph Theory. KyotoCGGT 2007. Lecture Notes in Computer Science 4535 68-78 DOI:10.1007/978-3-540-89550-3_7
  6. Fukuda H, Mutoh N, Nakamura G, Schattschneider D 2007 A Method to Generate Polyominoes and Polyiamonds for Tilings with Rotational Symmetry Graphs and Combinatorics 23[Suppl] 259-267 DOI:10.1007/s00373-007-0719-y
  7. 福田 宏, 清水 道夫, 植松 正吾, 勝矢 光昭 2001 「映進対称性を持つフラクタル・テクスチュアパターンの生成」 情報処理学会論文誌 42(5) 1194-1197 IPSJ-JNL4205015, CinNi PDF
  8. 福田 宏, 別宮 利昭, 西山 靜, 中村 義作 2003 「平面タイル貼りに関する二つの話題」 『形とシンメトリーの饗宴』 小川 泰, 三浦 公亮, 増成 隆士, 三田村, Denes Nagy/監訳 第2部 幾何学的アートと形態学 25 pp.250-257 (森北出版社)
  9. Fukuda H, Betumiya T, Nishiyama S, Nakamura G 1996 Two topics on plane tiling KATACHI ∪ SYMMETRY 231-238 (Springer Tokyo) ISBN:4431701613 preprint, kilin:software
  10. Fukuda H, Saito T, Nakamura G 1994 Classification and computer generation of necktie patterns FORMA 9 67-72 DOI:scipress, RG:preprint, kilin:software

万能マス / Universal measuring devices without gradations


(a) 6合

(b) 3合  (c) 1合
図1

図2
六合マスは,次のようにして1合から6合までの酒を酒樽からお客の容器に測り入れることができます。 これを,一般化して,次のように,目盛りのないマスでの酒を測る事ができます。 「酒樽で酒をすくい,マスの直線上にない3頂点で水面を決めて,お客の容器の上と,酒樽の上で交互に酒をこぼすことを繰り返す」

底面が三角形の万能マス: 図2のような,底面が三角形,高さが h1, h2, h3 の側面をもつマスを考えます。このマスで,上の測り方で1合からn合まで酒が測れる時,最大のnは41で,そのマスは, (h1, h2, h3)=(12,13,16) です。つまり41合マスです。

未解決問題: マスの底面が長方形の場合,最大のnを求めて下さい。 計算機探索で見つかった最大のnは691で,そのマスは2種類あり, (h1, h2, h3, h4)=(1,32,83,691), (2,64,166,691) です。しかし,これ以上大きなnがあるかどうか解っていません。

  1. 秋山 仁『知性の織りなす数学美―定理づくりの実況中継』 (中公新書 2004/5)
  2. Akiyama J, Fukuda H, Nara C, Sakai T, Urrutia J 2008 Universal Measuring Boxes with Triangular Bases American Mathematical Monthly 115(3) 195-201
  3. Akiyama J, Fukuda H, Nakamura G 2003 Universal Measuring Devices with Rectangular Base eds Akiyama J, Kano M Discrete and Computational Geometry. JCDCG 2002. Lecture Notes in Computer Science 2866 1-8 (Springer, Berlin, Heidelberg) DOI:10.1007/b11261
  4. Akiyama J, Fukuda H, Nakamura G, Sakai T, Urrutia J, Zamora-Cura C 2001 Universal measuring devices without gradations Discrete and Computational Geometry, JCDCG 2000. Lecture Notes in Computer Science 2098 31-40 (Springer) DOI:10.1007/3-540-47738-1_2

超立方体と超正多面体 / Hyper-cube and regular polytope

図1図2

図3

図4
高次元の多面体(polytope)を見る方法には3通りあります。障子に映る影のように射影を見るか,展開して展開図を見るか,切断して切断面を見るかです。 図1は立方体(cube)を平面に射影した図,図2は展開図です。展開図は11通り,切断面は3,4,5,6角形の4通りあります。

論文2では,図3のような4次元の超立方体(hyper-cube)の3次元展開図が261通りあることを数え上げ,その全ての図を掲載しています。 論文3では,図4のような5次元の立方体の4次元切断面が484通りあることを数え上げ,その全ての図を掲載しています。

  1. Fukuda H, Shimizu M, Nakamura G 2000 Coloring of Polytopes in Four Dimensions HyperSpace 9 No.1 8-12 CiNii
  2. Fukuda H, Yasuike T, Shimizu M, Nakamura G 1998 Three-Dimensional Development of a Hyper-Cube in Four Dimensions HyperSpace 7 No.1 33-43 Graphics: VRML
  3. Fukuda H, Muto N, Goto K, Nakamura G 1997 Sections of hyper-cube in five dimensions FORMA 12 15-33 DOI:scipress, preprint, kilin:software