ボロノイ図に関する小さな考察

　先日、@sada1110 先生から「ボロノイ図において、点が重複している場合はどうなるか」というご下問を頂いた。
　考えてみたのだが、結構奥が深い。そこで、まずは問題を簡素化して考えてみることとした。

基礎的な事項と仮定

　Ｎ個の点群Ｐ（p₁,p₂,･･･，p_N）が与えられている時、任意の点Ｑに対して、Ｑから最も近いＰの点がどの点であるかに応じて平面を塗り分けたものがボロノイ図である。
　ボロノイ図は、有限個の線分又は半直線で平面を区切った図になる。半直線の数は、Ｐを含む最小の凸多角形の辺数に等しい。線分の数はちょっと簡単な計算方法が思いつかない。
　点群Ｐが１点だけからなる時は意味がないので、Ｐは２点以上からなるものと（以下常に）仮定する。
　点群Ｐが２点（p₁,p₂）だけからなる時は、ボロノイ図は、p₁,p₂の垂直二等分線になる。
　点群Ｐが３点（p₁,p₂,p₃）からなる時は、ボロノイ図は点群Ｐを三角形と見て、この三角形の外心（外接円の中心）を端点として各辺の中点を通るような３本の半直線となる。

　点群Ｐが４点以上の点で構成される場合は、一挙に記述が複雑になる。（一旦、この場合は脇に置いておく）

　当面、簡単にするために、点群Ｐは３点（Ａ，Ｂ，Ｃ）から構成されているものとし、点Ｂ，Ｃが極めて接近した場合におけるボロノイ図の挙動を考える。

　「極めて接近」の意味は、計測解像度δを下回る距離まで点Ｂ，Ｃが接近すること、と定義しておく。このとき、点Ｂ，Ｃの位置は必ずしも同一になる必要はないことに注意する。

座標の導入

　点群Ｐの座標として、Ａ（0，a），Ｂ（x、ε），Ｃ（-x、-ε）とする。ただし、x もεも正負いずれの値も取り得るものとし、a は x，ε，δ のいずれよりも十分に大きな値であるものと仮定しておく。
　このとき、 $\sqrt{x^2+\epsilon^2}<\frac{1}{2}\delta$ となれば、点Ｂ，Ｃは「極めて接近している」ことになる。
　考えるべきことは、εの値をδより小さい任意の値に固定しておいて、ｘを０に近づけた時のボロノイ図の挙動である。

εが０の場合

　まずは、最も簡単なケースから考える。
　ｘが０でなければ、△ＡＢＣは二等辺三角形である。外接円の中心は、 $0, \frac{a}{2}$ のすぐ近く（僅かに下方）にあり、ボロノイ図はほぼＴ字形になる。実際には、Ｔの字の横棒は僅かに折れ曲がっていて、Ｖ字を左右に引っ張ったような形をしている。

　この状態で x を 0 に近づけると、外接円の中心は $0, \frac{a}{2}$ に収束し、ボロノイ図はＴ字に収束する。
　ただし、x が 0 になった瞬間に△ＡＢＣは２点ＡＢに縮退するので、ボロノイ図も直線 $y=\frac{1}{2}a$ で分割される２枚の半平面に縮退する。

εが正の値（＜δ）の場合

　ｘがδよりも十分大きな値の場合は、△ＡＢＣは鋭角三角形であり、外接円の中心は△ＡＢＣの内部にある。しかし、ｘがある程度小さくなると、△ＡＢＣは鈍角三角形になり、外接円の中心は△ＡＢＣの外部に出てしまう。具体的には、外接円の中心はどんどん左に移動してしまう。
　この状態で x を 0 に近づけると、外接円の中心は $-\infty, \frac{a}{2}$ に近づく。
　（計算は省略しているが、それほど難しくはない。ここでは幾何学的直感を重視して書いている）

　ただし、x が 0 になった瞬間に３点ＡＢＣは一直線上に並ぶので、外接円は定義されなくなり、ボロノイ図は２本の直線 $y=\frac{1}{2}$ a - \epsilon $$ ， $y = 0$ で区切られる３つのエリアに分けられる。これは、幅が $\frac{1}{2}a$ の帯と、その上下の２枚の半平面である。

εが負の値（＞-δ）の場合

　εが負の値の場合は、εが正の値の場合の鏡像と考えて差し支えない。
　従って、x を 0 に近づけると、外接円の中心は $+\infty, \frac{a}{2}$ に近づく。
　ただし、x が 0 になった瞬間に３点ＡＢＣは一直線上に並ぶので、外接円は定義されなくなり、ボロノイ図は２本の直線 $y=\frac{1}{2}$ a - \epsilon $$ ， $y = 0$ で区切られる３つのエリアに分けられる。これは、幅が $\frac{1}{2}a$ の帯と、その上下の２枚の半平面である。
　

ということは？

　２点が計測限界よりも接近してしまった場合に、２点の相互位置は分からなくなるが、これを顕微鏡で拡大してみたばあいの２点の位置関係によって、ボロノイ図の挙動が大きく３通りに別れることが分かった。つまり、ボロノイ図の挙動は安定的ではない。
　実際には、点Ａを含むエリアは安定していて、点Ｂと点Ｃを含むエリアが不定になるだけである。点Ｂと点Ｃの位置は（検出限界を下回って接近しているので）不明となるので、点Ｂと点Ｃを含むエリアが不定になるのはおかしくない。

結局どういうこと？

　ボロノイ図は、２点がどれだけ接近しても、数学的に同一の座標を持たない限り計算できてしまう。
　ここで、座標の検出限界（下限）を設けることは、座標系を離散化するに等しい。離散空間において２点が検出限界を下回って接近している場合は、それら２点の座標を同一視することになるが、２点がどのような経路で接近するかによってボロノイ図の挙動が大きく変わりうることが分かった。

　もともと、ボロノイ図とは、「任意の点から見て、一番近い指定点はどれか、を返す図」である。指定点が縮合してしまえば、一番近い指定点が一意に決まらなくなるのは当然である。

　この場合、考察に意味を持たせるためには、追加の仮定が必要になるものと思われる。すなわち、

縮合している複数の点は１点として扱い、属性値が複数あるものと見なす
縮合している複数の点は全て返すように、ボロノイ図を多価関数ベースで考える

　のいずれかである。（両者は本質的には同じことであるが）

多価ボロノイ図

　多価ボロノイ図においては、ボロノイ分割を行う前に、与えられた点群のうち限界距離以下に接近しているものを縮合しているものと見なして１点にまとめるような前処理が必要になる。
　たとえば、４点（Ａ，Ｂ，Ｃ，Ｄ）が与えられ、このうち点Ｂ、Ｃの距離が限界よりも近い場合は、点集合（Ｂ，Ｃ）を一点と見なして、改めて３点（Ａ，Ｅ，Ｄ）でボロノイ分割を行うべきなのである。
　このとき、点Ｅの位置は、（Ｂ、Ｃ）の近傍の１点（接近限界で規定されるような分解能で得られる代表点）としておく他はない。

　実際には、接近限界としては「同一の筆にある地点であるかどうか」が代表的であろう。集合住宅のように、単一の底地の上に複数の世帯が存在している場合、地番は同一で、住居表示で区別される。一般的には、住居表示が示す位置は、底地（敷地）である土地の代表点（筆の幾何学的中心とか、敷地の正門の位置とか）になるので、
ボロノイ分割を行った場合に多価関数として返す以外に方法はないと思われる。

より直感的な多価ボロノイ分割（１）

　私「Ｂさん、いま何処にいるの？」
　Ｂ「Ａくんと同じ所にいるのよ！」
　Ｃ「geo80k から見て一番近いのは誰だ？」
　私「（Ａ，Ｂ）の二人だね！」
　（Ａ，Ｂ）「私たち、ずーっと一緒！！」

　どちらも区別できない（実生活では距離を区別しない）のは明らかである。

より直感的な多価ボロノイ分割（２）

　私「Ｂさん、いま何しているの？」
　Ｂ「Ａくんとワルツを踊っているのよ！」
　Ｃ「geo80k から見て一番近いのは誰だ？」
　私「（Ａ，Ｂ）がくるくる回っているから決められないよ！」

　無理に一価関数にしようとすると、こうなる。彼らは所詮二人で一つなのであって、「 a couple of 」を前置するのに適しているというわけだ！

ちょっと直感的ではない多価ボロノイ分割（笑）

　原子核の周囲を数個の電子が回っている。
　たとえば、ヘリウム原子の周囲には２個の電子が回っている。

　この２個の電子は、完全に同一の地点に来ることはないから、古典的な原子核モデルにおいては、電子の位置に基づく幾何学的なボロノイ分割が可能で、ほぼヘリウム原子核の位置を通るような平面で空間が分割される。

　しかし、高速に動き回る電子でボロノイ分割することの意義はほぼ皆無であろう（ヘリウムを絶対零度ちかくまで冷やして、原子核の位置をほぼ固定したとしても）。

　さらに、電子の位置を確率分布にしたら（いわゆる電子雲だ）？　ボロノイ図も確率分布になるのか？（ちょっと書きすぎ）

玄天黄地

学生時代、箸にも棒にも掛からなかったアホの子が、やっと普通のアホになれるか？