ボロノイ図の形について

質問

ボロノイ図において、点がn点あるとし、n→∞としたときには何角形になるのでしょうか？
オイラーの多面体定理を用いて求められるそうなのですが、どなたか説明してもらえませんか？

よろしくお願いします。

回答No.5

info22

#1,#3です。
A#3の補足について
>円になるのは分かったのですが、オイラーの多面体定理（頂点-辺+面=2）を用いて証明することは出来ないでしょうか？

1点の周りの多角形では、母点の数nのとき最大で(n-1)角形と(n-1)頂点の多角形が作れますので、オーラーの多面体定理を適用すると
今は立体をつぶした平面で考えますので(面数)は裏表重なっていると考えて2となります。
母点がnのとき中心の母点を除く他の母点を円周上に等間隔（必ずしも等間隔でなくて適当な間隔をあけても良い）に並べていくとすると、できるボロノイ図の多角形の頂点数(n-1)と辺数(n-1)にできます。それらと面数との間にオイラーの多面体定理
(頂点数)-(辺数)+(面数)=2
(n-1)+(n-1)+2=2
が成立します。
このオイラーの多面体定理の関係式が、nが大きくなっても常に成り立つならば、n→∞のときボロノイ図の正(n-1)角形の辺数=頂点数（n-1）の関係を保ちながら(n-1)→∞になって辺数と頂点数が無限大になり、円に収束することがいえることになりますね。

回答No.4

Tacosan

「形が異なる」ことは理解できたんですよね. だとしたら, 結局 #2 の疑問に戻ります: どこの形を考えているのですか?
その説明もなく「オイラーの多面体定理を用いて求める」といわれても, 誰にも理解できません.
もっと端的にいえば: あなたが何を求めているのかさっぱり分かりません.

回答No.3

info22

#1です。
A#1の３）の参考URLのボロノイ図クリック編を使って1点の周りのボロノイ多角形を、手書きで円周上に並ぶように母点を選んでいくといくつでも母点を増やしていけますので（添付図が1点の周囲に16点まで並べてn=17点で16角形ができました）、nを大きくしていくと(n-1)多角形ができます。
なのでn→∞で限りなく円に近い辺数n-1の（正）多角形ができるようです。中心の点と円周上に等分割に(n-1)点を並べて行くと、できるボロノイ多角形の極限の円の半径は「中心点と点を円周上に並べた円の半径」の1/2になります。n→∞ではボロノイ多角形は(n-1)角形なので円に限りなく近づくといえますね。

ドロネー多角形は基本的には三角形で、特異なケースで四角形になる場合があるということです。n→∞としても基本的には三角形ですね（上の(n-1)ボロノイ多角形の極限だとほとんど潰れて線分状になった三角形です）。
参考URL）
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/voronoi-diagram/voronoi-diagram.html

補足

回答ありがとうございます。
円になるのは分かったのですが、オイラーの多面体定理（頂点-辺+面=2）を用いて証明することは出来ないでしょうか？

回答No.2

Tacosan

「何角形になる」というのは, どこのことを指しているのでしょうか?
ボロノイ分割して得られる各領域は通常形が異なりますよね.
「ドローネ三角形分割」はその名の通り, 通常三角形になりますが....

補足

やはり形が異なりますよね…
ある形に収束するのかなと思っていたのですが。

回答No.1

info22

ボロノイ図の多角形の定義はどうなっていますか？
ドロネー多角形とは違いますね？

参考URL
１）http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/algorithm/voronoi-diagram/voronoi-diagram.html
２）http://www.yk.rim.or.jp/~ans/SUBI/GIF/SU/TOK/20.gif
３）http://www.nirarebakun.com/voro/voro.html
４）http://www.yk.rim.or.jp/~ans/SUBI/vor.html

補足

１つの点の周りの形でお願いします。
しかし、ドロネー多角形もｎを∞とした時に求められるのなら、
そちらの解説ももしよろしければよろしくお願いします。