結び目の近傍抜き出しソフトウェア

谷研究室 伊藤雄祐

2006年2月10日

結び目のイメージ

研究背景

目的

数学者とソフトウェア

デモンストレーション

曽根英則氏のソフトウェアとの比較

まとめ

目次

結び目のイメージ

研究背景

目的

数学者とソフトウェア

デモンストレーション

曽根英則氏のソフトウェアとの比較

まとめ

目次

結び目のイメージ

紐を交差させたもののモデル。

両端を繋げたもの

太さを持たない

伸縮自在

結び目の定義

三次元空間上の有限の線分による

自己交差しない閉じた折線を結び目とする

結び目のイメージ

研究背景

目的

数学者とソフトウェア

デモンストレーション

曽根英則氏のソフトウェアとの比較

今後の課題

目次

結び目理論の応用

量子コンピュータ

遺伝子

暗号

生化学

合成化学

統計力学

http://www.linnaeus.uu.se/online/fysik/mikrokosmos/fylevande.html

http://www-gene.hep.phen.mie-u.ac.jp/haba/seminar_042/butsuri.html

http://www.bio.is.ritsumei.ac.jp/~t-imai/research.html

http://www.ph.tokushima-u.ac.jp/~syn/ao/ao_top.htm

同値のイメージ

結び目を伸ばしたり縮めたり交差させたりして

同じような形になれば同じ結び目と言える

結び目理論の基本的問題

二つの結び目は同じか？(同値性判定)

カットせずにその結び目をほどくことができるか？

（自明性判定）

結び目の変形などから

解を得るのが難しい

結び目を膨らませる

The computational Complexity of Knot and Link Problems

JOEL HASS et al.など重要で一般的な概念

空間の定義

四面体を単位として交差させずに

密に並べたものを空間とする

三次元空間上の辺に結び目を描く

結び目の近傍

結び目を膨らませる = 結び目の近傍を選択する

空間上の辺に

結び目がある

結び目に隣接した四面体の集合
= 結び目の近傍

結び目のイメージ

研究背景

目的

数学者とソフトウェア

デモンストレーション

曽根英則氏のソフトウェアとの比較

まとめ

目次

目的

結び目の近傍を抜き出すソフトウェアを作る

→曽根英則氏の引き継ぎ

結び目のイメージ

研究背景

目的

数学者とソフトウェア

デモンストレーション

曽根英則氏のソフトウェアとの比較

今後の課題

目次

数学者は射影図で結び目を描く

結び目の表現方法としてポピュラーなのが射影図

射影図は立体的な

イメージを平面に

投影したもの

上下関係が分かるように

奥の線を途切れさせる

結び目の近傍抜き出しソフトウェアを
扱いたいのは数学者

数学者にやさしいソフトウェアとは

数学者はプログラマではない。

→コーディングするのに特化したデータよりも

視覚的なイメージで入出力することが

数学者にとっては有用

視覚的イメージは数学者をより支援することができる

数学者に取って使いやすい
結び目のソフトウェアとは

射影図を描くことで入力することにより

結び目の近傍を含めた立体的なイメージを

作成し、描画するソフトウェアは

数学者に対して有用

作成したソフトウェア

射影図をGUIで入力

交差点の上下の情報の抽出

空間を生成し入力した結び目を埋め込む

近傍を取る

描画

結び目のイメージ

研究背景

目的

数学者とソフトウェア

デモンストレーション

曽根英則氏のソフトウェアとの比較

今後の課題

目次

デモンストレーション

閉じた折線で射影図により入力できる

簡便である

近傍のイメージを取得できる

結び目のイメージ

研究背景

目的

数学者と結び目

デモンストレーション

曽根英則氏のプログラムとの比較

今後の課題

目次

曽根英則氏のソフトウェアとの比較(1)

曽根氏の作成したソフトウェア

ランダムに作った立体イメージの中から希望の結び目に近いエッジを選択する

今回発表したソフトウェア

射影図から立体的なイメージを作成する

曽根英則氏のソフトウェアとの比較(2)

曽根氏の作成したソフトウェア

ソース上で入力

今回発表したソフトウェア

GUIで入力

曽根英則氏のソフトウェアとの比較(3)

曽根氏の作成したソフトウェア

入力が三次元

より複雑なデータを用意せねばならない

今回発表したソフトウェア

入力が平面

より複雑なデータを自動生成する

結び目のイメージ

研究背景

目的

数学者と結び目

デモンストレーション

曽根英則氏のプログラムとの比較

まとめ

目次

まとめ

射影図をGUIで入力

交差点の上下の情報を抽出

空間に埋め込む

近傍を取得

描画

今後の課題

可視性の向上

近傍を利用したアルゴリズムの実装

結び目の近傍抜き出しソフトウェア

終

結び目の定義

単位円周から三次元上への単射連続写像

三角形分割

平面的な図形に三角形からのみなるように

辺や頂点を足すこと

四面体分割

三次元的な図形に四面体からのみなるように

頂点や辺や面を足すこと

三角形への重心細分

三角形に対し各頂点その対辺の中点を結ぶと6つの三角形が得られる

各々の線分の交点は重心

四面体への重心細分

四面体のを構成する各面である三角形を
重心細分してできる各々の三角形と
四面体の重心を結ぶことで24個の四面体を作れます

各面の重心と対となる頂点を結んだ交点が重心

結び目の近傍

結び目を含む空間を四面体分割して
二度重心細分する

結び目に隣接した四面体の集合が近傍

表示しているもの

速度を上げるために

結び目の近傍から結び目につながる辺を

削除したものを表示している

立体イメージの作成手順

各面の三角形と
柱の重心を結んで
四面体にする

各側面を重心により

三角形に分ける

射影図の情報から選ぶ

三角形分割する

二重にして

三角柱にする

The computational Complexity of Knot and Link Problems

JOEL HASS et al.より

2006-02-07T17:02:34