OpenGLによる結び目の 近傍抜き出しソフトウェア 情報システム解析学科　谷研究室 5404025　澄川 知弘

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレ－ション ５．まとめ

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

結び目とは ３次元における自己交差しない閉曲線

結び目とは ３次元における自己交差しない閉曲線 直感的に・・・１本のゴム紐の両端を繋いだ輪っか

結び目の基本的問題 「同型判定」 ？

結び目の基本的問題 「同型判定」 2 つの結び目 K, K' に対し、S3 × [0, 1] 上の 自己同相写像 H と自己同相 h: S3 → S3 の組で次の条件 ・h(K) = K' ・H|S3×{i} (for all i ∈ [0, 1]) は S3 × {i} 上の同相写像 ・H|S3×{0} = idS3, H|S3×{1} = h を満たすものが存在するとき、 　K と K' は同値な結び目であるという ？

することで同じ形に変形できるかということ （紐を切って繋ぎ直すのは×） 結び目の基本的問題 「同型判定」 　　見た目の違う２つの結び目が、 　　同じ結び目であるかどうか 　→　伸ばしたり、縮めたり、ねじったり 　　　することで同じ形に変形できるかということ 　　　（紐を切って繋ぎ直すのは×） ？

結び目理論の応用 量子コンピュータ 遺伝子 暗号 生化学 合成化学 統計力学 図２ 図１ ※図１ http://www.rothamsted.ac.uk/notebook/courses/guide/dnast.htm ※図２ http://www.bio.is.ritsumei.ac.jp/~t-imai/research.html

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

目的 「結び目の近傍を抜き出すこと」

太さを持たない結び目に太さを持たせよう！！ 目的 「結び目の近傍を抜き出すこと」 太さを持たない結び目に太さを持たせよう！！ 近傍を抜き出すことは、同型判定を行う時に役立つ

目的 「OpenGLとC言語のみで作成する」

目的 「OpenGLとC言語のみで作成する」 LEDAライブラリは使わず、座標計算のみで実装

目的 「OpenGLとC言語のみで作成する」 LEDAライブラリは使わず、座標計算のみで実装 プラットフォームに依存せず、無償で稼動する

様々なコンピュータ環境で稼動！！ 目的 「OpenGLとC言語のみで作成する」 LEDAライブラリは使わず、座標計算のみで実装 プラットフォームに依存せず、無償で入手可能 様々なコンピュータ環境で稼動！！

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

近傍を求める手順 １）入力 ２）三角形分割 ３）結び目の３次元表示 ４）四面体分割

近傍を求める手順 １）入力 ２）三角形分割 ３）結び目の３次元表示 ４）四面体分割 Joel Hass, Jeffrey C. Lagarias and Nicholas Pippenger による "The Computational Complexity of Knot and Link Probrems" Journal OF THE ACM Vol. 46 pp.185-211 (March 1999)　を参照

入力 １．結び目の射影図をマウス描画で入力

入力 １．結び目の射影図をマウス描画で入力 射影図・・・３次元である結び目を２次元で表したもの

入力 １．結び目の射影図をマウス描画で入力 ２．交差してる部分の上下関係を コマンドラインから入力 射影図・・・３次元である結び目を２次元で表したもの ２．交差してる部分の上下関係を 　　コマンドラインから入力

三角形分割 入力された図形を三角形分割する

三角形分割 入力された図形を三角形分割する

三角形分割 入力された図形を三角形分割する

三角形分割 図形がすっぽり収まるような大きな三角形を配置する

三角形分割 図形がすっぽり収まるような大きな三角形を配置する

三角形分割 適当に線を引いて三角形分割

結び目の３次元表示 ２次元から３次元に視点を変える

Z=-1とZ=1平面に先ほど分割した図形を配置する 結び目の３次元表示 Z=-1とZ=1平面に先ほど分割した図形を配置する Z Y X

結び目の３次元表示 交差の上下関係の情報から線を引く Z Y X

結び目の３次元表示 交差の上下関係の情報から線を引く Z Y X

四面体分割 平面同士向かい合う頂点に線を結ぶ

四面体分割 平面同士向かい合う頂点に線を結ぶ 三角柱がいっぱい出来る！！

四面体分割 三角柱１つ１つにおいて

四面体分割 側面に対角線を引く

四面体分割

四面体分割

四面体分割 三角柱の重心を求める

四面体分割 三角柱の重心を求める ここ

四面体分割 各頂点から重心に線を結ぶことで四面体を１４個作る

四面体分割 四面体１つ１つにおいて

四面体分割 四面体を構成する面を６つの三角形に分ける

四面体分割 四面体を構成する面を６つの三角形に分ける

四面体分割 四面体の重心を求める

四面体分割 四面体の重心を求める ここ

四面体分割 各頂点から重心に線を引き、四面体を２４個作る

四面体分割 作られた四面体１つ１つにおいて 　同様の四面体分割をもう１度行う

四面体分割 作られた四面体１つ１つにおいて 　同様の四面体分割をもう１度行う

近傍の取り方

近傍の取り方 平面同士向かい合う頂点に線を結ぶ 四面体がいっぱい！！

３次元表示で表示した結び目の辺の情報をもとに 近傍の取り方 ３次元表示で表示した結び目の辺の情報をもとに Z Y X

近傍の取り方 辺に隣接する四面体だけを抜き取る

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

目次 １．結び目について ２．今回の研究の目的 ３．近傍の求め方 ４．デモンストレーション ５．まとめ

OpenGLの実装について

OpenGLの実装について ・WINDOWS＆LINUX共に稼動 ・若干、ウインドウ表示が不安定 　（線描写や色の付き具合） ・LEDAライブラリ使用に比べて 　ソースコードが膨大

今後の課題

ある２つの結び目の近傍のデータを用意して、 その２つのデータを圧縮した時の類似度が、 結び目の同型判定に役立てることが出来るか調べる 今後の課題 ある２つの結び目の近傍のデータを用意して、 その２つのデータを圧縮した時の類似度が、 結び目の同型判定に役立てることが出来るか調べる 絡み目の近傍も抜き出せるように プログラムを拡張させる プログラムの精度を上げる （見やすさの向上、バグ除去・・・）

→ダイアグラムをデータとするファイルを用意 先輩方との比較 2006度（加藤・田村さん）の入力 　→ダイアグラムをデータとするファイルを用意 ・多重点は横断的な　 ２重点のみを持ち ・交点に交差の上下　 と辺の出る順番の　 情報をもつグラフ　 として考える － ＋ １ ＋ － ＋ － ２ － ＋

先輩方との比較 2005年度（伊藤さん）の入力 　→GUIにより射影図をマウス描画で入力

先輩方との比較 2004年度（曽根さん）の入力 　→用意してある頂点の中から希望の結び目に近い 　　頂点を選び、データをソース上で入力

結び目の同値性 位相幾何学では、連続写像を用いて連続的に変形して互いに一致させる ことができる図形は同相といって、一般に同じものであると考える。 結び目理論も位相幾何学の理論であるから、同様な同一視を 行うのであるが、しかし如何なる結び目も円周 S1 と同相であるので、 同相であるかどうかを見るだけではどんな結び目も 区別することはできない。そこで、与えられた結び目が、ある結び目を 切ったり貼ったりすることなく連続的に変形していったものと 一致するなら、もともと 2 つの結び目は同じであったと考える。 これは、結び目のみならずその周辺の空間まで含めて 連続的に変形できるかどうかということであって、以下のように定式化される。 2 つの結び目 K, K' に対し、S3 × [0, 1] 上の自己同相写像 H と 自己同相 h: S3 → S3 の組で次の条件 h(K) = K' , H|S3×{i} (for all i ∈ [0, 1]) は S3 × {i} 上の同相写像, H|S3×{0} = idS3, H|S3×{1} = h を満たすもの（アンビエント・アイソトピック）が 存在するとき、K と K' は同値な結び目であるという。

ライデマイスター移動

なぜ三角形・四面体か？ 平面において一般の多角形は 三角形の集合に分割できる。 三角形より小さいもの（頂点数が少ない図形）は 存在しない。 つまり平面で最小のものが三角形であるため 三角形分割を行う。 ３次元においても同様に、 四面体が最小のものであるため、 四面体分割を行う。

近傍

近傍

近傍

近傍

近傍

近傍 原型とは程遠い・・・

近傍

近傍

近傍

近傍

近傍 穴の開いてる部分が出来て、原型らしくなった！！

なぜ２回の単体分割か？ 近傍をとったときにソリッドトーラスと同相に したくて、2回やらないとその保証が無い。 逆に言えば2回重心細分して近傍をとれば 必ずソリッドトーラスと同相になる。 トーラスとはドーナツのような形状をした 図形のことである。 トーラスの囲む中身が詰まったものを意味するときには、 特にソリッド・トーラス、輪環体などのようにいう。