最適配置の数理
2.4 ボロノイ図の一般化
Ｖ(pi)＝{p｜d(p,pi)≦ d(p,pj)，j≠i ，j=1,2,…,n}
2.4.1 線のボロノイ図
点からでなく、線ごとに最も近い領域を示すボロノイ図
ラインごとに、そのラインが最も近い点を集めてできる領域をＶ(li)とし、それを集めてできる幾何図形を線分ボロノイ図呼ぶ。
Ｖ(li)＝{p｜d(p,li)≦ d(p,lj)，j≠i ，j=1,2,…,n}
2.4.2 面ボロノイ図
- 線のボロノイ図と同じように、今度は線の変わりに面で考える。
- ある点ｐから面Ｓｎまでの距離をd(p,Sn)とする。
- ある面Ｓiが最も近い点pの集合をＶ(Ｓi)としこの領域を面ボロノイ領域と呼ぶ。
- 面ボロノイ領域が集まってできる幾何図形を面ボロノイ図と呼ぶ。
2.4.3 オーダmのボロノイ図
- 今までの仮定１（施設の利用者は最も近い施設を利用する）でなく、一番目に近いか二番目に近い施設を利用するという仮定で考えてみる。
- 母点piとpjが一番目と二番目に近い点pが集って出来る領域をＶ(pi,pj)とし、これを「母点がpi，pjよりなるオーダ２のボロノイ領域」と呼ぶ。
Ｖ(pi ,pj)＝{p｜d(p,pi)≦d(p,pk)， d(p,pj)≦d(p,pk)，i≠k，j≠k，k=1,2,…,n}となる
- これらの領域が集って出来る幾何図形をオーダ２のボロノイ図と呼ぶ。
母点の置き方によっては、領域Ｖ(pi,pj)が領域をもたない事もある。
- オーダmのボロノイ図は、n個の母点あるならmの上限はn−１となる。
- i以外がn−１までに近い領域＝iが一番遠い領域となるのことより、オ−ダ（n−１）のときそのボロノイ領域は、ある母点が最遠点となる領域となる。このボロノイ図を最遠点ボロノイ図と呼ぶ。
2.4.4 重み付きボロノイ図
- 通常ボロノイ図では、母点に差異が無いとして仮定１（施設の利用者は最も近い施設を利用する）を使ったが、もし母点ごとに差異があるとすると、仮定１が使えなくなってしまう。
- 例として、教科書P.45 L.25からの条件で考えてみると、仮定３（消費者は、Pi＋t･ d(p,pi)が最小である店で買う）が成り立つとし、仮定３と仮定２に基づいて母点piの領域を求めると
Ｖ(pi)＝{p｜Pi＋t･d(p,pi)≦Pj＋t･d(p,pj)，j≠i，i=1,2,…,n} 式（2.8）とあらわせる
- この領域Ｖ(pi)は母点ごとの重みの差によって導かれた領域なので重み付きボロノイ領域と呼ばれる。
- これらの重み付きボロノイ領域からなる全体の幾何図形を重み付きボロノイ図と呼ぶ。
2.4.5 マンハッタン距離のボロノイ図
- マンハッタン距離のボロノイ図では、図2.31のような碁盤目状の道路での最短路を考える。
- 例として図2.31の点ｐ(x,y)から点ｐi(xi,yi)へ行く最短路は破線のようになり、この距離を数式を使って表すと、
- ここで、直線距離で一番近い施設を利用するという仮定の代わりに、マンハッタン距離で一番近い施設を利用すると仮定すると、その領域がどうなるかを考える。
- そうすると図2.32のように２つの施設が道に対して４５°，１３５°の直線上にある時、網点部の領域では、どちらの施設も等距離となる。このような場合便宜的に図2.32のように分けると、
2.4.6 カールスルーエ距離のボロノイ図
環状放射状道路網での２点間の最短距離は、２点の相対位置によって通ったり通らなかったりする。図2.35
点p(θ,r)点pi(θi,ri) ２点間の距離d(p,pi)は、
@ d(p,pi)＝r*δ(θ,θi)＋｜r−ri｜，
点p(θ,r)点pi(θi,ri) ２点間の距離d(p,pi)は、
点p(θ,r)点pi(θi,ri)２点間の距離d(p,pi)は、
@ d(p,pi)＝r*δ(θ,θi)＋｜r−ri｜，
カールスルーエ距離によるボロノイ図は図2.36のようになる。
2.4.7 その他の一般ボロノイ図
- マンハッタン距離のボロノイ図、カールスルーエ距離のボロノイ図を組み合わせて一般化し一般的な道路網上でのボロノイ図も作る事が出来る。
- ボロノイ図は２次元空間に限らず、一般化してn次元空間のボロノイ図を考える事も出来る。
- 他にも、球上のボロノイ図、シリンダー上のボロノイ図、コーン上のボロノイ図、トーラス上のボロノイ図、多面体上のボロノイ図、障害物があるときのボロノイ図、なども研究されている。