2014-01-12

穴あき曲面の展開

Math

f:id:tkenichi:20131229133334j:plain

閉曲面（いわゆる境界のないコンパクトな曲面）の分類はよく知られていて、曲面に切れ目を入れて展開した多角形を張り合わせることで表現することができる。向き付け可能な場合は球面またはg個のトーラスの連結和として表すことができ、多角形の張り合わせで表現する場合は、以下のようになる。

$a_1 b_1 a_1^{-1} b_1^{-1} \cdots a_g b_g a_g^{-1} b_g^{-1}$

向き付け不可能な場合は、射影空間のk個の連結和としてあらわすことができる。多角形の張り合わせで表現する場合は、以下のようになる。

$a_1 a_1 \cdots a_k a_k$

さて、閉曲面から開円板を取り除いた境界つきの曲面の多角形表現を考えよう。ここでは、展開した多角形の頂点（張り合わせたときに曲面上の１点になる）を含むように開円板をとる。すなわち、開円板の境界が展開した多角形のすべての辺と交叉する場合を考える。向き付け可能な場合は以下のようになる。

$a_1 d_{2g} b_1 d_{(2g-1)} a_1^{-1} d_{(2g-2)} b_1^{-1} d_{(2g-3)} \cdots a_g d_4 b_g d_3 a_g^{-1} d_2 b_g^{-1} d_1$

向き付け不可能な場合は以下のようになる。

$a_1 d_1 a_1 d_2^{-1} \cdots a_k d_{(2k-1)} a_k d_{(2k)}^{-1}$

曲面	オイラー数	多角形展開した時の辺の個数
g 個のトーラスの連結和	2-2g	4g
k 個のトーラスの連結和	2-k	2k
g 個のトーラスの連結和から開円板を除いたもの	1-2g	8g
k 個のトーラスの連結和から開円板を除いたもの	1-k	4k

拡張された三角形分割の個数を数えるには、境界つきの曲面の多角形表現で、境界上にすべての頂点があるような場合で、展開した多角形を平面上の三角形分割すればよい。ただし、重複するものが現れるので、それを除く必要がある。

2013-12-23

多角形を三角形分割２

Math Programming

f:id:tkenichi:20131207161434j:plain

平面上の多角形の三角形分割を列挙するプログラムを作成してみた。先日の記事で紹介したような拡張された三角形分割ではなく、総数がカタラン数で与えられるような三角形分割である。

def catalanEach(ary)
	case ary.size
	when 2
		yield []
	when 3
		yield [ary]
	when 4
		yield [ [ary[0],ary[1],ary[2]],[ary[0],ary[2],ary[3]]]
		yield [ [ary[0],ary[1],ary[3]],[ary[1],ary[2],ary[3]]]
	when 5
		yield [ [ary[0],ary[1],ary[2]],[ary[0],ary[2],ary[3]],[ary[0],ary[3],ary[4]]]
		yield [ [ary[0],ary[1],ary[2]],[ary[0],ary[2],ary[4]],[ary[2],ary[3],ary[4]]]
		yield [ [ary[0],ary[1],ary[3]],[ary[1],ary[2],ary[3]],[ary[0],ary[3],ary[4]]]
		yield [ [ary[0],ary[1],ary[4]],[ary[1],ary[2],ary[3]],[ary[1],ary[3],ary[4]]]
		yield [ [ary[0],ary[1],ary[4]],[ary[1],ary[2],ary[4]],[ary[2],ary[3],ary[4]]]
	else
		(2...(ary.size)).each{ |i|
			t = [ [ary[0],ary[1],ary[i]] ]
			a0 = [ ary[0] ]
			a1 = [ ary[1] ]
			(2...(ary.size)).each{ |j|
				if j < i
					a1 << ary[j]
				elsif j == i
					a1 << ary[j]
					a0 << ary[j]
				else
					a0 << ary[j]
				end
			}
			catalanEach(a0){|t0|
				catalanEach(a1){|t1|
					yield (t+t0+t1)
				}
			}
		}
	end
end

2013-12-08

多角形を三角形分割

Math

f:id:tkenichi:20131207155348j:plain

四角形を三角形に分割する方法は2通り、5角形を三角形に分割する方法は5通りある。この個数は一般にカタラン数というもので与えられ、一般にn+2角形を三角形に分割する方法は

$\frac{1}{n+1}\begin{pmatrix}{2n\\n}\end{pmatrix}$

通りである。

さて、実は上の定義は平面上における凸多角形の三角形分割の個数である。より一般に高次元の多角形、または単に組み合わせ的な三角形への分割を考えると、少し分割の仕方が増える。たとえば5角形の場合、頂点を1,2,3,4,5とすると

[1,2,4] [1,3,4] [1,3,5] [2,3,5] [2,4,5]

のような分割がある。これは5角形の辺をメビウスの輪の境界にするような分割の方法である。

6角形の場合は

[1,2,3] [1,3,5] [1,4,5] [1,4,6] [3,4,6] [3,5,6]

のようなメビウスの輪の境界にするような分割のほかに

[1,2,4] [1,3,5] [1,3,6] [1,4,5] [2,3,5] [2,4,6] [2,5,6] [3,4,6]

のような、トーラスに穴を開けた曲面の境界（穴の部分）が6角形の辺となるような分割の方法もある。これは6角形が非自明な結び目になるときの組み合わせ的なザイフェルト曲面になると考えられる。

さて、このような拡張された三角形分割の個数を表にしてみた。

頂点数	3	4	5	6	7	8	9	一般形
三角形分割数	1	2	5	14	42	132	429	カタラン数
拡張された三角形分割数	1	2	6	30	337	?	?	?

一般形は何だろう？三角形分割数がカタラン数を介して括弧のつけ方やヤング図形と関連しているのと同様に、拡張された三角形分割数は他の何かと関連しているのだろうか？？

もう少し詳しい表（Tをトーラス、Pを射影平面、Sを球面、Dを開円板とする）
? は計算中の値

頂点数n	三角形分割の位相	3	4	5	6	7	8	9	10	一般形
(n-2)個の三角形分割数	S-D（閉円板）	1	2	5	14	42	132	429	1430	カタラン数 http://oeis.org/A000108
n個の三角形分割数	P-D（メビウスの輪）	0	0	1	14	113	720	4033?	?	http://oeis.org/A007817
(n+2)個の三角形分割数	T-D	0	0	0	2	70	1144	12354?	?	?
(n+2)個の三角形分割数	2P-D	0	0	0	0	112	2400	28593?	?	?
(n+4)個の三角形分割数	3P-D	0	0	0	0	0	3944?	?	?	?
(n+6)個の三角形分割数	2T-D	0	0	0	0	0	0?	?	?	?
(n+6)個の三角形分割数	4P-D	0	0	0	0	0	1772?	?	?	?
(n+8)個の三角形分割数	5P-D	0	0	0	0	0	32?	?	?	?
拡張された三角形分割数		1	2	6	30	337	10144?	?	?	?

2013-11-24

最小コストな路線ネットワーク

Math

f:id:tkenichi:20131116135942j:plain

次のような問題を考えよう。

まだ鉄道が敷かれていない複数の駅を連結するような最小の路線ネットワークを作る。このとき、それぞれの駅間を線路でつなぐためのコストが与えられているとして、最小のコストで実現できる路線ネットワークは何か？

駅を頂点、線路を辺とするグラフを考えると、コストは辺に重みが与えられていると考えられ、最小の路線ネットワークとはグラフの最小全域木（Minimum Spanning Tree）であるから、最小全域木の全体で、それを構成する辺の重みの和を最小化するものを求める問題になる。

グラフの最小全域木は、いわゆるマトロイドの代表例である。この問題はマトロイドの最適化の問題に帰着される。マトロイドを計算するようなプログラムはまだ少ないのだけれど、この種類の問題をとくことができるものが COIN-OR に紹介されていた。

https://projects.coin-or.org/MOCHA

抽象化されたマトロイドに対して最適化を解けるわけではなく、グラフとベクトルからなるマトロイドについて、計算できるというものだが、問題そのものをこれらのどちらかに帰着すればよいので、使い道はありそう。

2013-09-16

穴の個数を数える

Math

f:id:tkenichi:20130728102412j:plain

入力としてデジタル画像を与えて、色がついていないところを穴として、いくつあるかを数えるソフトウェアはあるだろうか？2次元図形の穴の個数を数えるということは、ホモロジー群を計算するということである。計算ホモロジーという分野が最近発展しているらしく、最初の問いに答えるようなソフトウェアもフリーソフトウェアとして公開されている。それが CHomP である。*1

http://chomp.rutgers.edu/

雨の連休中に少し触ってみた。いくつかのコマンドラインプログラムの集まりになっていて、GUI はコマンドライン引数を与えるランチャーがある程度であるので、使いこなすのはちょっと難しいかもしれないが、面白い機能がいくつかある。

2次元の画像と閾値を与えて、集合（2つ閾値を与えて集合対を与えることもできる）を定義し、そのホモロジー群を計算してくれる。たとえば、東京の地下鉄の路線図をなぞってみた図形

f:id:tkenichi:20130916181101j:plain

のホモロジー群は、0次が Z で、1次が Z^74 と計算してくれる。それ以外に単体複体を組み合わせ的に与えたときも計算してくれるし、3次元の立方体集合（ここでは cubical set といっているが voxel のようなもの）を与えたときのホモロジー群も計算できる。

つまり、3次元のポリゴンデータやCTなどのボクセルデータのホモロジー群が（変換プログラムを作る必要はあるが）計算できるようになるということである。これで今まであまり定量化できなかった性質が見えてくると面白そう。

*1:chompで検索すると別のコマンドプログラムがヒットしてしまうので、注意

2013-08-16

ピアニストの脳を科学する

Book

f:id:tkenichi:20130721132451j:plain

ピアニストの脳を科学する超絶技巧のメカニズム

作者: 古屋晋一
出版社/メーカー: 春秋社
発売日: 2012/01/23
メディア: 単行本（ソフトカバー）
購入: 7人クリック: 91回
この商品を含むブログ (16件) を見る

人間が記憶する能力は言語化によるところが大きいのだと思っていました。しかし、音楽家は暗譜しています。それは楽譜をそのまま覚えるのではない。音楽家がどのように脳を使っているかの研究結果によると、暗譜は視覚野の神経回路を活用しているそうで、かつ、楽譜の情報を圧縮して記憶しているそうです。

また、ピアニストが俗に指に覚えさせる、と言いますが、実際にはピアノを弾くために脳を進化させるのだそうです。たとえば、音楽を聴いただけで指を動かすための神経細胞が活動するとのことです。ピアノの先生が言う脱力する、という意味も鍵盤を叩くのに重力や慣性力をうまく利用してるということもわかってきているそうです。

ピアノ演奏の技術を、医学と工学の立場から解明しようとしていて、たくさんの驚きがある本。今まで芸術家の感覚としてしか説明できなかったことを、科学的に説明しようとする大胆な試み。面白かった。

2013-07-07

6つの辺からなる閉じた折れ線が三葉結び目になる条件（２）

Math

f:id:tkenichi:20130430151824j:plain

前回説明した内容の補足である。
ここでは常に
$\triangle P_1 P_2 P_3$ と $\triangle P_4 P_5 P_6$ がホップ絡み目 $L_{123-456}$
$\triangle P_2 P_3 P_4$ と $\triangle P_5 P_6 P_1$ がホップ絡み目 $L_{234-561}$
$\triangle P_3 P_4 P_5$ と $\triangle P_6 P_1 P_2$ がホップ絡み目 $L_{345-612}$
が同時に成り立つ場合を考えることにする。

補題１
$\triangle P_1 P_3 P_5$ と $\triangle P_2 P_4 P_6$ は2成分の自明な絡み目である。

補題２
ホップ絡み目 $L_{123-456}$ のザイフェルト曲面 $Z_{123-456}$ は
$\{ \triangle P_1 P_3 P_5, \triangle P_3 P_4 P_5, \triangle P_2 P_3 P_4, <br /> \triangle P_2 P_4 P_6, \triangle P_1 P_2 P_6, \triangle P_1 P_5 P_6 \}$
または
$\{ \triangle P_1 P_3 P_5, \triangle P_3 P_5 P_6, \triangle P_2 P_3 P_6, <br /> \triangle P_2 P_4 P_6, \triangle P_1 P_2 P_4, \triangle P_1 P_4 P_5 \}$
で与えられる。