修士論文発表資料

円ボロノイ図の厳密計算法に関する研究
数理情報学第 5 研究室 修士 2 年 田中快明
指導教員 杉原 厚吉 教授
平成 18 年 2 月 7 日

1

本研究の概要Ps

円ボロノイ図とは円を生成元として作成したボロノイ図であr3る [2]．円ボロノイ図の逐次添加による構成アルゴリズムを考

p3

えた際に最も重要になるのが，ボロノイ頂点を形成する 3 円がr3

P1

P1p3

P3

P3P0
r0 p0

共通に外側から接する円に対して新しく追加する円が共通部分p1を持つかどうかという判定である．本研究ではこの判定を行う方法を考え，厳密計算手法を適用したとき必要となる精度を見

rs

r1p2

p1

r1p2r2積もる事を行った．本研究で提案する手法では，3 円に共通にpsr2

P2P2

外側から接する円が 2 つ存在する場合の必要な精度は，この共通に外側から接する円が 1 つしか存在しない場合の必要な精度(a) 共通内接円 P0と比べて非常に大きいものになってしまっている．

2(b) 共通外接円 Ps

図 1: 3 円 Pi = {pi , ri }, i = 1, 2, 3, に対する (a) 共通内接円

定義

P0 = {p0 , r0 }，および (b) 共通外接円 Ps = {ps , rs }．実線が中心 p，半径 r の円を {p, r} と表す．円 Pi = {pi , ri }, i = 3 円を，点線がその 3 円による共通内接円または共通外接円を1, . . . , n, の円ボロノイ図は次式で表されるボロノイ領域 Vi , i = 表す．
1, . . . , n, の集合であるとする．
変換後も他の円と接している状態を保つように半径の変換を与2
Vi = {p ∈ R |d(p, pi ) − ri < d(p, pj ) − rj , i 6= j}. (1) える．

3

本研究ではボロノイ頂点を形成する 3 円と添加される新しい円との関係のみに着目するので，3 円の添え字を 1,2,3，添加する円の添え字を 4 とする．また，4 番目の円が最小である，すなわち，判定法以下の 3 つの関数を判定に利用する．

r4 ≤ r1 , r2 , r3 であると仮定する．3 円 Pi = {pi , ri }, i = 1, 2, 3,に対して次の 2 つの特別な円を定義する．

F = A21 + A22 − A23 ,図 1(a) のように 3 円 P1 , P2 , P3 が円 P0 = {p0 , r0 } に外側から接しているとき，円 P0 を円 P1 , P2 , P3 の共通内接円と呼ぶ．
また，図 1(b) のように円 Ps = {ps , rs } に内側から接している
とき，円 Ps を円 P1 , P2 , P3 の共通外接円と呼ぶ．

3 円 P1 , P2 , P3 およびその共通内接円 P0 と共通外接円 Ps に

R = A3 /2A,¯¯ 1 x1¯¯¯ 1 x2L(x, y) = − ¯¯
¯ 1 x3¯¯ 1 xy1y2y3

¯
¯ x0
¯ 1
¯A = ¯ x02¯¯ x0¯r10 ¯¯¯r20 ¯¯r30 ¯

対して，次の変換を施した後のパラメータを 0 をつけて表す． ここで，x0i = xi − x4 , yi0 = yi − y4 , ri0 = ri − r4 ,(2)i = 1, 2, 3,

3x00 = x0 − x4 , y00 = y0 − y4 , r00 = r0 + r4 ,(3)x0s = xs − x4 , ys0 = ys − y4 , rs0 = rs − r4 .

(4)

(5)

y10y20y30y¯
r1 ¯¯¯r2 ¯¯.
r3 ¯¯¯r4 ¯

(6)

(7)

であり，Ai は A を定める行列の第 i 列を (w10 , w20 , w30 )T で置き換えた行列の行列式である．また，wi0 = (x0i )2 +(yi0 )2 −(ri0 )2 , i =1, 2, 3, である．

この変換は 4 番目の円 P4 が原点へ縮小するようにパラメータ

各関数はそれぞれ次のような性質を持っている．関数 F はを変更する変換である．共通内接円と共通外接円に関しては， (i)4 番目の円が 3 円の共通内接円に外側から接している場合

1[1]，(ii)4 番目の円が 3 円の共通外接円に内側から接している
場合の 2 つの場合で 0 になる関数である．このうち (i) の場合

llは，3 円の共通内接円に新しく添加する円が接するという境界

P'02

P'sP'2になる重要な状況であるが，(ii) はまったく関係ない場合であ

P'1

P'01る．関数 R は前述の F = 0 となる 2 つの場合に対して，(i) のP'0

場合は R > 0，(ii) の場合は R < 0 となる関数である．

3.1r'01p'01

p'02
r'02

P'3

共通内接円と外接円が 1 つずつある場合

共通内接円と共通外接円が 1 つずつある場合，変換を施した後の様子は図 2(a) の通りとなる．このとき L(x, y) = 0 で表さ(a)(b) 共通外接円 Ps

れる直線 l に対して，3 円 P1 , P2 , P3 は同じ側に存在する．直線 l に対してこの 3 円と同じ側では外側に共通外接円，内側に

図 2: (a) 共通内接円と共通外接円が 1 つずつ存在した場合，共通内接円が存在する．一方，反対側では外側に共通内接円， (b) 共通内接円が 2 つ存在した場合，の各場合における変換後内側に共通外接円となる．これと，関数 F と R の符号を参考の様子．にすることにより 4 番目の円が他の 3 円の共通内接円と交わる
この方法に必要な精度は次の通り莫大になってしまう．(10)かどうか判定する条件が得られる．4 番目の円が直線 l に対し式のように定めると，判定の過程で最も精度が必要となる項は，て 3 円と同じ側にあるとき，条件は次の通りになる．

F < 0, かつ R > 0.

(精度が最も必要な項) ∼(8)

一方，3 円と反対側にあるときは，条件は次の通りとなる．

F > 0, または (F ≤ 0 かつ R < 0).

M 416
M 408

(13)

である．

(9)

4

まとめと今後の課題

よって，関数 L(x, y) を用いて上述の 2 つの場合を判定した後，本研究では，ボロノイ頂点を形成する 3 円の共通内接円に対関数 F と R の符号を調べることで判定が行える．

して添加する円が交わっているかどうか判定する判定法の流れ

この判定に必要な精度は次の通り見積ることができる．

について述べた．この判定は，円ボロノイ図の逐次添加による−M ≤ xi , yi , ri ≤ M(10)構成アルゴリズムを考えた際に，最も重要となる判定である．
また，この判定を行うのに必要な精度の見積もりを行った．とすると，関数 F が最も精度を必要とし，今後の課題として，共通内接円が 2 つ存在する場合のより必|F | < 216 M 8(11)要精度が低い判定法の構築が挙げられる．現在の手法は非常に大きい精度が必要になっている．共通内接円と共通外接円が 1である．

つずつある場合は入力の 8 倍程度の精度で済むので，より必要精度の低い判定法を考える必要がある．

3.2

共通内接円が 2 つある場合

参考文献

共通内接円が 2 つある場合，変換後の様子は図 2(b) の通り[1] M. L. Gavrilova and J. Rokne: Updating the topologyof the dynamic Voronoi diagram for spheres in Euclideanとなる．この場合直線 l と平行な方向に 4 番目の円と同じ半径を持つ円を動かし，4 番目の円の両側に零点が何個あるかとい

d-dimensional space. Computer Aided Geometric Design,
vol. 20 (2003), pp. 231–242.

うことを調べれば判定することができる．これは 4 番目の円の中心 (x4 , y4 ) を (12) 式の値に変えて得られる関数 FQ (t) の区
間 (−∞, 0) および (0, +∞) における零点の数を調べることで知ることができる．
¯¯ ¯
¯ 1
¯ x1 1 r 1 ¯¯¯¯¯¯ ¯
 − ¯ x2 1 r 2 ¯ t + x4 , ¯ 1¯¯¯¯ 1¯ x3 1 r 3 ¯y1y2y3

¯

r1 ¯¯
¯r2 ¯ t + y4  .
¯r3 ¯[2] A. Okabe, B. Boots and K. Sugihara: Spatial Tessellations– Concepts and Applications of Voronoi Diagrams. John
Wiley and Sons, 1992.

(12)2