ボロノイ図 - らんだむな記憶

ボロノイ図 - Wikipediaとかいうやつを計算幾何などの本でよく見かける。英語のwikiのほうが詳しそうだが...: Voronoi diagram - Wikipedia, the free encyclopedia

計算幾何学と地理情報処理第2版 / 伊理正夫監修腰塚武志編集 | 共立出版などは結構気合の入った本で、複体やらボロノイ図やらそういうのがかなり出てくる。
それ以外でもグラフィックスの数理 / 杉原厚吉著 | 共立出版やタンパク質構造とトポロジー ―パーシステントホモロジー群入門― / 三村昌泰竹内康博森田善久編集平岡裕章著 | 共立出版でも見かける。おっと全部共立出版じゃないかw

ご利益のよく分からない代物だが、見かけるようになったので性質だけ探っておく。
まず、定義としては、

定義

$\mathbb{R}^d$の有限個の点集合$\{x_i \in \mathbb{R}^d;\ i = 1,\cdots, m\}$に対して、
\begin{equation}
V_i := \{ x \in \mathbb{R}^d;\ |x - x_i| \le |x - x_j|,\ 1 \le j \le m,\ j \neq i \}
\end{equation}
とする。この$V_i$をボロノイ領域と呼ぶ。

記号を追加する。$H_{i,j} := \{ x \in \mathbb{R}^d;\ |x - x_i| \le |x - x_j| \}$と置く。この時、$V_i = \cap_{j \neq i}H_{i,j}$である。
さて、ボロノイ領域では有限個の点集合しか扱わないのだろう。重要な性質として以下がある。
※以下、適当に探ったので証明はエレガントではない。

命題1

$\mathbb{R}^d = \cup_{i = 1}^m V_i$

証明

$\mathbb{R}^d \setminus \cup_{i = 1}^m V_i = \varnothing$とする。$x \in \mathbb{R}^d \setminus \cup_{i = 1}^m V_i$をとる。この時$x \not\in V_i,\ 1 \le i \le m $なので、${}^\exists H_{1,j_1},\cdots, H_{m,j_m} \quad \mathrm{s.t.}\quad x \not\in H_{1,j_1},\cdots,\ x \not\in H_{m,j_m}$がとれる。
ここで、写像$\varsigma:\ i \mapsto j_i $を考える。仮に、$ 1 \mapsto 3,\ 3 \mapsto 4,\ 4 \mapsto 1 $のような置換
\begin{equation}
\begin{pmatrix}
1 & 3 & 4 \\
3 & 4 & 1
\end{pmatrix}
\end{equation}
が見出せる場合、$x \not\in H_{1,3},\ x \not\in H_{3,4},\ x \not\in H_{4,1}$であるので、逆順で見ていくと、
\begin{equation}
|x - x_1| < |x - x_4| < |x - x_3| < |x - x_1|
\end{equation}
で矛盾が生じる。よって、写像$\varsigma$によるインデックスの対応表は置換を含まない。しかし、これ自身矛盾である。
と言うのも、置換が生じないためには
\begin{align}
&\varsigma(1) \in \{1,\cdots,\ m\} \setminus \{ 1 \},\ \varsigma^2(1) \in \{1,\cdots,\ m\} \setminus \{ 1,\ \varsigma(1) \}, \\
&\varsigma^3(1) \in \{1,\cdots,\ m\} \setminus \{ 1,\ \varsigma(1),\ \varsigma(2) \}, \cdots
\end{align}
である必要がある。もし$\varsigma^j(1) = \varsigma^i(1)\ (i < j)$が成立すると、$\varsigma^i(1) \to \varsigma^{i+1}(1) \to \cdots \to \varsigma^j(1) = \varsigma^i(1)$で置換が生じるからである。
しかしこの場合、$\varsigma^m(1) \in \varnothing$となり、$H_{m,j_m}$が存在しないことになり矛盾である。${}_\blacksquare$

これでボロノイ領域による空間分割は全空間を覆うことが分かった。

定義

ボロノイ領域による空間$\mathbb{R}^d$の分割をボロノイ図と呼ぶ。

さて、各ボロノイ領域はどのように交わっているのであろうか？

命題2

$i \neq j$の時$V_i$の内部と$V_j$の内部の共通部分($\mathring{V_i} \cap \mathring{V_j}$)は空集合である。

証明

$V_i$の内部は$\{ x \in \mathbb{R}^d;\ |x - x_i| < |x - x_j|,\ 1 \le j \le m,\ j \neq i \}$である。$x \in \mathring{V_i} \cap \mathring{V_j} \neq \varnothing$とすると、$|x - x_i| < |x - x_j| < |x - x_i|$となり矛盾である。${}_\blacksquare$

これでボロノイ領域同士は共通部分を持つとしてその境界上に限られることが分かった。
次に、ボロノイ領域が凸集合であることを見たいが、その前に補題を用意する。

補題1

$\widetilde{H_{i,j}} := \{ x \in \mathbb{R}^d;\ \langle x - \frac{1}{2}(x_i + x_j),\ x_i - x_j \rangle \ge 0 \}$とおく。ここで$\langle \cdot,\cdot\rangle$は標準内積を表す。
この時、$\widetilde{H_{i,j}} = H_{i,j}$が成立する。

証明

\begin{align}
&\langle x, x_i - x_j\rangle - \frac{1}{2}\langle x_i + x_j, x_i - x_j\rangle \ge 0 \\
\iff & \langle x,\ x_i\rangle - \langle x,\ x_j\rangle - \frac{1}{2}(|x_i|^2 + |x_j|^2) \ge 0 \\
\iff & |x|^2 - 2 \langle x,\ x_i\rangle + |x_i|^2 \le |x|^2 - 2 \langle x,\ x_j\rangle + |x_j|^2 \\
\iff & |x - x_i|^2 \le |x - x_j|^2 \iff |x - x_i| \le |x - x_j|
\end{align}
より。${}_\blacksquare$

上記は$x_i$と$x_j$の中点を通り$x_i - x_j$に直交する余次元1の超平面で分断される$x_i$側の半分が$H_{i,j}$だ、という主張である。

命題3

各$V_i$は凸集合である。

証明

凸集合同士の共通部分は凸集合なので、$H_{i,j}$が凸であることを見れば良い。
$H_{i,j}$を$\frac{1}{2}(x_i + x_j)$だけ平行移動して点$\frac{1}{2}(x_i + x_j)$が原点に重なるようにする。
従って、補題1より、$H_{i,j} = \{ x \in \mathbb{R}^d;\ \langle x,\ x_i - x_j \rangle \ge 0 \}$が凸であることを見れば良い。
$x,\ y \in H_{i,j}$とし、$0 \le t \le 1$をとる。
\begin{equation}
\langle (1-t)x + ty,\ x_i - x_j \rangle = (1-t) \langle x,\ x_i - x_j \rangle + t \langle y,\ x_i - x_j \rangle \ge 0
\end{equation}
より主張を得る。${}_\blacksquare$

ボロノイ図からその双対としてドロネー図、脈体(nerve complex)としてドロネー複体が得られるらしく(この2つは同じ？異なる？まだ理解していない)、これも重要なようだ。

―――――・・・

ちょっとggるとタンパク質構造とトポロジー ―パーシステントホモロジー群入門― / 三村昌泰竹内康博森田善久編集平岡裕章著 | 共立出版の著者に関係するドキュメント類が見つかる。

あまり難しいのは分からないので、リンクを張るだけで雰囲気だけ出してみる。
どっかのサイトで計算幾何やらパーシステントホモロジーについて以下の本があがっていたが、未知の領域な上に洋書なのでしんどいな。
Amazon.co.jp： Computational Topology: An Introduction: Herbert Edelsbrunner, John L. Harer: 洋書

http://pantodon.shinshu-u.ac.jp/topology/literature/persistent_homology.htmlによると、パーシステントホモロジーは上記洋書の著者のEdelsbrunner氏らが画像認識を計算機で行うために導入したものらしい。

Persistent homology を用いて様々なデータを分析することを topological data analysis (TDA) と言ったりする。

と書いてあるように、Topological data analysis - Wikipedia, the free encyclopediaというデータ解析の領域でも使われているらしい。
DeepLearning - Deep Learning の次は、TDA 「トポロジカル・データ・アナリシス」 (Topological data analysis) が来る ? ～その概要と、R言語 / Python言語実装ライブラリをちらっと調べてみた - Qiitaにもあるように、深層学習(Deep learning; 多層ニューラルネットワーク)に次いで最近注目されているようだ。しっかし、お腹いっぱいだわな。
まったくもってまともに勉強したことのない幾何学と代数学のコンビネーションが多いので、もうイミフメス。

ただ、上記のタンパク質本はいまのところ、パーシステントホモロジーの唯一の和書らしいし、そもそもそれを除いても、ホモロジーの幾何学的イメージをつかみやすい解説がなされており、また代数学の初歩の説明もあるので色々と入門書として良さそうに見える。但し、有名な(？)有限生成アーベル群の基本定理などは$\mathbb{Z}$-加群に限定して説明されているなど、一般的なR加群の話は出てこないようなので、加群に興味が出たらAmazon.co.jp：加群十話―代数学入門 (すうがくぶっくす): 堀田良之: 本あたりで更に追求するのも良いのだろう。
しかし、残念ながらpureな代数にはあまり関心はなく、作用素環のような解析チックな範囲でしか代数には興味がわかない。
幾何も超局所解析やハミルトン力学で見られるような余接バンドルとかその辺くらいでしか興味がわかないなぁ。

―――――・・・

はてなブログではσやτをMathJaxで書いておくと、MathJaxのプリプロセスが走る前に、blog機能のリンクが張られてしまい、MathJax側のパースエラーを起こすことが分かった。標準偏差とか書けないじゃないか...。