このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

［参照用 記事］

n次元空間の境界の向き

雑記／備忘

向き付きn次元多様体の境界である(n - 1)次元多様体に向きを誘導する、って話がありまして、思っていた以上にややこしいです。何が恣意的選択で何が必然的法則なのか？ 僕は混乱してしまいました。

多様体をベクトル空間にしても向きの議論は同じ（少なくとも局所的には）なので、有限次元ベクトル空間のセッティングで、分かる範囲で整理してみます。

内容：

半空間が指定された有限次元ベクトル空間

nを1以上の自然数として、V を実数体上のn次元ベクトル空間とします。有限次元Rベクトル空間には、標準的〈canonical〉な位相が入るので、その位相も考えます。

W \subset V を、(n - 1)次元部分ベクトル空間とします。差集合 V\setminus W は（位相空間として）2つの連結成分を持つので、どちらか一方を選択して固定します。H \subset V を次のように定義します。

  • H := W\cup (\mbox{選ばれた連結成分})

位相の意味での開核 \stackrel{\circ}{H} は、最初に選ばれた連結成分です。補集合 H^c は、選ばれなかったほうの連結成分です。

以下、三つ組 (V, W, H) は与えられたもの〈given〉として固定します。

言葉を定義しておきましょう。ベクトル v\in V が：

  • v\in \stackrel{\circ}{H} のとき、内向きベクトルと呼ぶ。
  • v\in H^c のとき、外向きベクトルと呼ぶ。
  • v\in W のとき、境界方向ベクトルと呼ぶ。

基底とフレーム

ベクトル空間の基底とフレームは区別します。基底はベクトル空間の部分集合で、線形独立かつ生成的なものです。フレームは、基底の要素に全順序を入れた順序集合です。全順序構造は、「真に小さい」を表す関係 \lt で表すことにします。

B\subset V を基底として、F = (B, \lt) を集合 B 上に全順序を載せた順序集合、つまりフレームとします。\bar{n} := \{1, \cdots, n\}\mbox{ with total order} とすると、n要素の全順序集合は \bar{n} と順序同型になります。つまり、全順序を保存した同型写像が一意に存在します。

  • \psi : \bar{n} \to B 全順序 \lt を保存する同型

この同型写像の余域をベクトル空間 V にまで広げて、さらに線形に拡張すると、線形写像 f:{\bf R}^{\bar{n}} \to V が定義できます。ここで、 {\bf R}^{\bar{n}} = Map(\bar{n}, {\bf R}) は写像の空間ですが、{\bf R}^{\bar{n}} \cong {\bf R}^n \mbox{ as vecor spaces} なので、{\bf R}^{\bar{n}} を単なる数空間〈標準ユークリッドベクトル空間〉と考えてもかまいません。

以上から、次の三者は1：1に対応します。

  1. V のフレーム F = (B, \lt)
  2. 集合のあいだの同型 \psi : \bar{n} \to B
  3. 線形同型写像 f:{\bf R}^n \to V

ベクトル空間の向き

n次元ベクトル空間 V のすべてのフレームの集合を Frame(V) とします。F = (B, \lt), F' = (B', \lt') \in Frame(V) を2つのフレームとすると、次の図式を可換にする写像（疑問符のやつ）として、フレームのあいだの変換 \tau_{F/F'} を定義します。ここで、f, f' はそれぞれ、F, F'\in Frame(V) から誘導される線形同型写像です。

\require{AMScd} \begin{CD} {\bf R}^n @>{f}>> V \\ @V{?}VV @| \\ {\bf R}^n @>{f'}>> V \\ \end{CD}\\ \mbox{commutative}

もちろん、

  • \tau_{F/F'} := f'^{-1}\circ f: {\bf R}^n \to {\bf R}^n
  • f'\circ \tau_{F/F'} = f

\tau_{F/ F'} は数空間〈標準ユークリッドベクトル空間〉のあいだの線形同型写像なので、行列表示して非ゼロな行列式が得られます。この行列式を \det(\tau_{F/F'}) と書くことにします。

Frame(V) 上の同値関係 \sim を次のように定めます。

  • F \sim F' :\Leftrightarrow \det(\tau_{F/F'}) \gt 0

この同値関係による商集合を、ベクトル空間 V の向き〈orientation〉の集合とします。

  • Orien(V) := Frame(V)/\sim

行列式の性質などから、Orien(V) が二元集合であることがわかります。

フレームへの置換群の作用

n次置換群〈n次対称群〉は、集合としての（順序は忘れた）\bar{n} の自己同型写像〈automorphism〉の群です。n次置換群を Perm(n) とします。

  • Perm(n) := Aut(\bar{n})

B \subset V を基底とすると、さきほど述べた1：1対応があります。

  1. \psi:\bar{n} \to B \mbox{ bijection}
  2. F = (B, \lt) \mbox{ frame (totally ordered set)}
  3. f: {\bf R}^n \to V \mbox{ linear isomorphism}

置換 \sigma \in Perm(n) = Aut(\bar{n}) があると、\sigma を \psi にプレ結合〈pre-compose〉できます。\psi' := \psi\circ \sigma とすると、それに応じてフレーム、線形同型写像も変化します。

  1. \psi' = \psi\circ \sigma :\bar{n} \to B \mbox{ bijection}
  2. F' = (B, \lt') \mbox{ frame (totally ordered set)}
  3. f': {\bf R}^n \to V \mbox{ linear isomorphism}

\psi^\sigma := \psi',\, F^\sigma := F',\, f^\sigma := f' と置けば、置換 \sigma は集合 Bijection(\bar{n}, B),\, Frame(V), LinearIso({\bf R}^n, V) のそれぞれに作用します。作用〈action〉を、右肩に置換を書いて示したわけです。

特に、Frame(V) への作用に注目すると、次の可換図式が存在します。

\begin{CD} Frame(V)\times Aut(\bar{n}) @>{action}>> Frame(V) \\ @V{orien\times sign}VV @VV{orien}V \\ Orien(V)\times Aut(\bar{2}) @>{action}>> Orien(V) \end{CD}\\ \mbox{commutative}

ここで、orien:Frame(V) \to Orien(V) は商集合への標準射影、sign:Aut(\bar{n}) \to Aut(\bar{2}) は、置換の符号〈パリティ〉を、二元群 Aut(\bar{2}) = \{identity, flip\} への写像とみなしたものです。符号1が identity、符号-1が flip です。

これは次のことを言っています。

  • フレームへの置換の作用に対して：
    • 偶置換は向きを変えない（恒等として作用する）
    • 奇置換は向きを変える（入れ替えとして作用する）

半空間と整合した正規直交フレーム

(V, W, H) は、最初の節で述べた、ベクトル空間 V に、（閉じた）半空間 H とその境界である部分ベクトル空間 W が指定された構造です。

W の補空間が欲しいのですが、補空間は一意に決まりません。V に内積が入っていれば補空間を一意に取れるので、V は内積ベクトル空間としましょう（内積が必須ではないが、便利だから）。W^\perp は W の直交補空間とします。W^\perp の次元は1です。

  • V = W^\perp\oplus W \mbox{ where }dim(W^\perp) = 1

ベクトル空間 V の基底（注意：フレームではない）B が、次の条件を満たすとき半空間（H \subset V のこと）と整合していると言うことにします。

  1. B = B' \cup \{b\} と書ける。
  2. B' は部分ベクトル空間 W の基底になっている。
  3. \{b\} は部分ベクトル空間 W^\perp の基底になっている。

V に内積があるので、以下、正規直交基底だけを考えることにします。B = B'\cup\{b\} が半空間と整合する正規直交基底のとき、次の二つのケースがあります。

  1. b\in W^\perp が内向きベクトルのとき
  2. b\in W^\perp が外向きベクトルのとき

半空間と整合した正規直交基底 B = B'\cup\{b\} に対して、全順序を入れたフレーム F = ( B'\cup\{b\}, \lt) を半空間と整合した正規直交フレームと呼びましょう。

向きを誘導する方法

V は内積ベクトル空間と仮定したので、フレームは正規直交フレームだけを考えます -- そのほうが色々と話が簡単になります。V の正規直交フレームの集合を ONFrame(V) とします。正規直交フレームに、その向きを対応させる写像と、置換群の作用は次のように定義されます。

  • orien:ONFrame(V) \to Orien(V)
  • action:ONFrame(V)\times Perm(n) \to ONFrame(V)

V に向きが決まっているとは、二元集合 ONFrame(V) のどちらかの要素が指定されていることです。「向き＝正規直交フレームの同値類」だったので、正規直交フレームを指定しても向きを指定したことになります。ただし、同じ向きを指定する正規直交フレームはたくさんあります。

V に向きが決まっているとき、半空間の境界である部分空間 W の向きを決める手順を向きを誘導する方法、あるいは短く向き誘導法と呼びます。向き誘導法はアルゴリズムとして記述されるべきものです。

V に向きを指定する正規直交フレームは、向きを変えない範囲で自由に選べるので、次の仮定を置いてもいいでしょう。

  • V に向きを指定する正規直交フレームは、半空間と整合した正規直交フレームだとする。

V の（必ずしも正規直交とは限らない）任意のフレームから、W^\perp \oplus W による直交分解とグラム／シュミット法を組み合わせれば、半空間と整合した正規直交フレームを構成できます。

向き誘導アルゴリズムは、“V の向きを与える半空間と整合した正規直交フレーム”をもとに、“W の向きを与える W の正規直交フレーム”を出力する手順です。

我々が興味を持つことは、向き誘導アルゴリズムのなかに、標準的と呼べるアルゴリズムがあるかどうか？ （もしあるならば）その標準的なアルゴリズムと他のアルゴリズムとの相互関係です。

アルゴリズムの妥当性

前節までで準備は終わりです。この準備のもとに向き誘導アルゴリズムを考えることは出来るのですが、何が標準的なアルゴリズムかはちょっと（僕には）分かりません。とりあえず、アルゴリズムが妥当である（悪くはない）条件を考えます。

F が V の半空間と整合した正規直交フレームだとして、それをベクトルのリストとして表現します。次のようです。

  • F = (f_1, \cdots, f_n)

フレームと基底の違いは：

  • F = (f_1, \cdots, f_n) \mbox{ ordered}
  • B = \{f_1, \cdots, f_n\} \mbox{ unordered}

リストとしてのフレーム F のどこかに W^\perp の要素がひとつだけ出現します。出現位置を k \mbox{ where } 1\le k \le n とします。F から f_k を取り除いたリストを G とします。例えば、k = 2 ならば、g_1 = f_1, g_2 = f_3, g_3 = f_4, \cdots となります。

素朴に考えて、与えられた長さnのリスト F から、上記の手順で得られた長さ(n - 1)のリスト G を使って W の向きを定めてはどうでしょうか？

この素朴な発想は、以下に説明する2つの点でウマクないようです。

F = (f_1, f_2, f_3, f_4) だとして、k = 4 の場合を考えてます。このとき、G = (f_1, f_2, f_3) で、このフレームが向きを定めます。F' = (f_2, f_1, f_4, f_3) とすると、F' は遇置換の作用で得られるので、向きの観点からは同値なフレームです。f_4 を取り除いて得られるフレームは G' = (f_2, f_1, f_3) で、G = (f_1, f_2, f_3) とは逆の向きになってしまいます。これはダメです。

前段落と同じセッティングで、F'' = (f_1, f_2, f_3, -f_4) とします。F'' は F とは逆の向きを定めます。が、4番目を除いて得られる W のフレームは同じものになってしまいます。ダメですね。

以上のことから次が分かります。

  • 遇置換の作用により影響を受ける（結果の向きが変わる）アルゴリズムはダメである。
  • フレームに含まれる W^\perp のベクトルが内向きか外向きかにより影響を受ける（結果の向きが変わる）アルゴリズムはダメである。

逆に言えば、ダメじゃないアルゴリズムの条件が得られます。

  • 遇置換の作用により結果の向きが変わらない。奇置換の作用によって結果は逆になる。
  • フレームに含まれる W^\perp のベクトルが内向きか外向きかにより結果の向きが変わらない。

最良のアルゴリズムはあるのか？

悪くないアルゴリズムの条件はわかったのですが、The best とか The standard なアルゴリズムってあるでしょうか？ 僕には、The best / The standard を決める基準がサッパリ思い付きません。幾何的あるいは物理的に意味がある基準があるのでしょうか？ ひょっとしてあるのかも知れませんが、僕の印象は、悪くないアルゴリズムならどれを採用しても同じじゃん、です。

悪くないアルゴリズムのひとつを提示しておきます。これが、The best / The standard と思っているわけじゃないです。

前節と同様に、与えられた V のフレーム F = (f_1, \cdots, ..., f_n) のk番目に W^\perp の要素が出現しているとします。1 または -1 の値を記録する変数 p, q を準備して、次の手順を実行します。

  1. k が奇数なら p = 1 、偶数なら p = -1 とセットする。
  2. f_k が内向きベクトルなら q = 1 、外向きベクトルなら q = -1 とセットする。
  3. リストとしての F から f_k を取り除いたリストを G とする。
  4. p×q = 1 なら、G の向きをそのまま採用する。p×q = -1 なら、G の向きと逆の向きを採用する。

もう一度繰り返すと、悪くないアルゴリズムはあっても、最良のアルゴリズムなんてない気がします。より正確に言えば、悪くないアルゴリズムのなかから最良のアルゴリズムを選ぶ基準がないような気がします。基準があったら教えて下さい。