グラフィックスハードウェアによるボロノイ図の描画とその周辺
Fast Drawing of Voronoi Diagrams Using Graphics Hardware and Related Topics
山本修身（名城大学・理工学部）

Osami YAMAMOTO (Meijo University)
キーワード： ボロノイ図，グラフィックスハードウェア
Keywords: Voronoi diagrams, graphics hardware

1.

はじめに
グラフィックスハードウェアは３次元図形を高速にコンピュータのディスプレイ上に描画するための専用ハードウェアである．近年では高級なワークステーションだけでなく，一般用途の多くのパーソナルコンピュータに，このようなグラフィックスハードウェアが搭載されている．グ
ラフィックスハードウェアの性能向上は近年めざましいものがあり，現在までのところ 12ヶ月で速度が 2 倍になっている．これは中央処理装置（CPU）の性能向上の速度よりも速い．また，近年では本来の 3 次元図形を描くための計算能力に加えて，ある種のプログラムをグラフィックスハードウェア内部に与えることによって，特殊な陰影付け
図 1: 頂点が同一平面上に置かれるように並べた円錐面を下から見た様子．それぞれの円錐面を固有の色で着色す
るとユークリッド平面上のボロノイ図となる．など，より複雑な計算を行わせる機能を備えている [2, 8]．
この機能は，グラフィックスハードウェア内部のプログラミングをある程度可能にするものであり，グラフィックスハードウェアを単に普通の画像の描画に利用するだけでフィックスハードウェアを用いてボロノイ図を描画するたはなく，より柔軟に色々な計算に利用する可能性を与えてめには，与えられた母点に対応する３次元図形を画面上にいる．

描画すれば良い．たとえば，ユークリッド平面上の n 個のボロノイ図は計算幾何学における基本的な手法の１つで母点 pi (i = 1, . . . , n) のボロノイ図は方程式あり多くの応用範囲を持つ．問題としている空間に幾つかの母点と呼ばれる点が与えられたとき，「どの母点に一番近z = kx − pi k2 (i = 1, . . . , n)

(1)

いか」という基準によって，その空間を分割したものがボで表現される n 枚の円錐面をそれぞれ母点固有の色で画ロノイ図であり，オペレーションズリサーチをはじめ種々面上に描画し，z 軸方向から眺めれば良い (図 1 参照) [4].の分野において幾何的あるいは地理的な問題を解くための3 次元グラフィックスライブラリ OpenGL [5, 10] を用い強力な道具となっている．各種のボロノイ図の計算アルゴて，この方法によって得られたランダムな 100 点のボロノ

リズムについては計算幾何学の発展と共に多くの研究が行

イ図を図 2 に示す．このようにして得られるボロノイ図とわれてきている [3, 6, 7, 9] ．

通常の方法によって得られるボロノイ図は本質的に異なる

本稿ではグラフィックスハードウェアによる各種ボロノものであり，ここで求めているものはあくまでボロノイ図イ図の描画について概観し，さらにボロノイ図の双対図形のイメージである．さらに，このイメージは連続的なものであるドローネ三角形分割や３次元凸包の計算に言及する．

ではなく，画面上のピクセル位置における色情報によってまた，最後の部分ではボロノイ図の描画効率について考察表現されたボロノイ図の概形に他ならない．一方，通常のする．

計算によって得られるボロノイ図は，それぞれの母点に対応する領域の形を頂点の座標として表現したものである．

2.

また，これは「画面の大きさ」や「ピクセルの細かさ」なグラフィックスハードウェアによるボロノイ図の原理どの制約を受けない．
グラフィックスハードウェア (GPU) は 3 次元空間中の前者の方法のメリットとして，種々のボロノイ図に対し図形を画面に表示するためのハードウェアである．グラてほぼ同じ原理で描画することができ，また，描画のため

1

図 2: ユークリッド距離に関するランダムな 100 点のボロノイ図.

図 3: マンハッタン距離に関するランダムな 100 点のボロノイ図.のプログラムも通常の方法とは比べ物にならないくらい単離が z であるような点 C(p, z) = {q ∈ R2 | d(p, q) = z}純であるということが挙げられる．ユークリッド平面上でが深さ z に配置されるような図形を描画すれば良い．このの通常のボロノイ図の描画については，多くの高速アルゴような図形は四角錐面となる．この図形を要素として用いリズムやプログラムが知られているが，そうではないボロれば，マンハッタン距離に関するボロノイ図を描くことがノイ図をこれほど手軽に描くことは難しい．

できる．図 3 にランダムな 100 点に関するボロノイ図を示す．

前述のユークリッド平面上のボロノイ図は，実はより簡グラフィックスハードウェアを用いれば，それぞれの母単に描くことができる．まず，前述の円錐面の代わりにつ点に重みのついたボロノイ図についても簡単に描画する

ぎの放物面を描くことを考える：

z = kx − pi k22 . (i = 1, . . . , n)ことができる．このようなボロノイ図の描画では，それぞ(2)

れの母点に対応した図形の形状を変化させればよい．ある

一般にグラフィックスハードウェアでは，3 次元空間中の複雑母点 x を中心として，そこから任意の点 y までの距離をな曲面を描くことは難しいが，この場合には，3 次元空間のd(x, y) = akx − yk + b のように測った場合，前述のユーすべての点に変換 ϕ : (x, y, z) ∈ R3 7→ (x, y, z−x2 −y 2 ) ∈クリッド距離に関するボロノイ図については，円錐面の開R3 を適用することによって，すべての放物面が平面き具合と深さ方向の位置をそれぞれ a, b に対応させて変えれば良い．また，このようなボロノイ図と多少異なったz = kpi k22 − 2(pi , x). (i = 1, . . . , n)(3)構造を持つものにラゲールボロノイ図がある．ラゲールボ
ロノイ図は距離を d(x, y) = kx − yk2 − r2 と定義したもに変換される．また，この変換は x 座標と y 座標を変えのである．r はそれぞれの母点に固有の量である．このよず，z 座標の大小関係を変えない．したがって，この変換

うなボロノイ図の領域の境界は直線であることが知られてによって得られる画面上のイメージは円錐面によって得らいる．ラゲールボロノイ図を作るためには，前述の放物面れたものと変わらない．方程式 (3) は平面を表すので，結を基に平面によって描かれるボロノイ図のアルゴリズムを果として n 個の母点に対応する平面を描画することによ変形し，n 枚の平面りボロノイ図が得られる．この変換によって描画速度を数

z = kpi k22 − 2(pi , x) − ri2 (i = 1, . . . , n)

倍高速化することができる [11]．しかし，それぞれのピクセルの深さを表現するバッファ (z バッファ) の精度が低(4)を描画すれば良い [11]．ランダムな 100 点に関するラゲー

いと，描画されるイメージが数値誤差により非常に不安定

ルボロノイ図を図 4 に示す．になることが知られており，ある程度高精度な z バッファ

つぎに，線分のボロノイ図について考えてみる．線分のボを用いる必要がある [11]．

ロノイ図は点と点との距離を線分と点との距離に置き換えた

同じ平面上のボロノイ図であっても用いる距離を変えた場ものである．線分は２つの平面上の２つの点 p1 と p2 を用い合，描画すべき要素の形状が変化する．たとえば，x 座標のて b = {λ1 p1 + λ2 p2 ∈ R2 | λ1 + λ2 = 1, 0 ≤ λ1 , λ2 ≤ 1}

差の絶対値と y 座標の差の絶対値の和を距離として定義すると定義できる．このとき，この線分と任意の点 p との距離

マンハッタン距離 d(p1 , p2 ) = |p1,x −p2,x |+|p1,y −p2,y | にはつぎのように表現される：よるボロノイ図を描くのであれば，断面が正方形になる同じ(形状の四角錐を描画すれば良い．ただし，p1 = (p1,x , p1,y ),d (b, p) =p2 = (p2,x , p2,y ) とする． すなわち，ある点 p からの距

2

kp1 − pk
ϕ(p1 , p2 , p)
kp2 − pkt ≤ 0,0 < t < 1,1 ≤ t.

(5)

図 5: 球面にランダムに分布した 80 母点による球面ボロノイ図．

図 4: 平面上のランダムな 100 点のラゲールボロノイ図．
ただし，ϕ(p1 , p2 , p) = (kp1 − pk2 kp1 − p2 k2 − ((p1 − p2 ) ·(p1 − p))2 )1/2 /kp1 − p2 k であり，t = (p1 − p) · (p1 −p2 )/kp1 − p2 k2 とする．この式から， 平面上の t ≤ 0 の部分と 1 ≤ t の部分には，通常のボロノイ図を描くための円錐面要素の一部を用いることができる．これに対して，

0 < t < 1 の部分は平面の一部である．これらの図形をそれぞれの線分に対応した色で描画すれば，線分のボロノイ図を描くことができる．
また，平面上のボロノイ図以外に球面上のボロノイ図を考えることもできる．この場合，球面上の２点間の距離は２点間の測地線の距離ということになる．球面の半径を 1として，球面上の２点の中心からの位置ベクトルを p1 お

図 6: 球面ボロノイ図を描画するための要素．

よび p2 とおくと，２点の距離はこの２つのベクトルの成す角に等しいことから，この曲面は球面を一次変換した楕円球の一部である (図 6d(p1 , p2 ) = cos−1(p1 , p2 )(6)参照)．この曲面を多角形近似した曲面を描画することにより得られる球面ボロノイ図を図 5 に示す．と表すことができる．ただし，(p1 , p2 ) は p1 と p2 の内積

本節ではグラフィックスハードウェアによる各種ボロノを表す．しかし，ここでボロノイ図を描くために必要なのイ図の描画について述べた．この方法の利点は，色々なボは大小の比較である．すなわち，与えられた各母点のうちロノイ図をほぼ同じ考え方の下で構成でき，原理の単純さ

どの母点に一番近いかを見つけ出すことができれば良い．

からボロノイ図を手軽に描画できることである．効率につしたがって，より単純に，いては本稿の後の部分で述べるが，用いるハードウェアにd(p1 , p2 ) = 1 − (p1 , p2 )依存し，いつでも高速に描画できるとは限らない．特に，(7)

これまで計算アルゴリズムが非常に良く研究されてきていと定義すれば十分である．この定義に基づき，球面上のあるユークリッド平面上のボロノイ図などについては，通常る点を p0 = (p0,x , p0,y , p0,z ) とおけば，通常のボロノイ図の方法で計算する方が効率が良いと考えられる．

を描くときに用いる円錐面に対応する曲面 Pp0 は，Sp0 = (0, 0, 1) − S20 A

3.

(8)

3 次元凸包とドローネ三角形分割の計算についてと表すことができる [11]．ただし，S2 は原点を中心とすグラフィックスハードウェアは本来画像を得るための道

る単位球面のうち z 座標が非正の部分であり，A はつぎの具であって，それ以外の用途に用いるために設計されていような 3 × 3 の行列である：

ない．しかし，描画した画像をメインメモリに転送するこ

ÃA=−1000−10p0,xp0,yp0,zとは可能であり，この機能を用いることにより，描画した!
.

画像から情報を得ることができる．

(9)

ドローネ三角形分割は２次元のボロノイ図の双対図形

3

y A(1/2,2)軸にとったグラフは図 7 の右図のようになる．この場合，

y-αxA

B(-1,1)D(1,1)
E(0,1)

それぞれの α について，値が最大および最小のものが実B際に凸包と接する直線と対応する．したがって，このようDな直線を実際に点固有の色で 3 次元空間にそれぞれ描画

Eして上方向または下方向から眺めた画像を構成すれば，そαC(0,0)

x-1

Cの方向の凸包を構成する頂点が見える．また，画像のなか1で，ある色から別の色に変化する境界は凸包上の辺に対応することがわかる．ある円盤中に一様に分布した 10 万点

図 7: グラフィックスハードウェアによる２次元凸包の計算の原理．の２次元凸包を計算する際のイメージを図 8 に示す．このイメージは 360 度を 90 度ずつ 4 つの方向に分け，それぞれの方向について計算しているので，４つの帯から成っている．このイメージで隣り合う色を列挙すれば，２次元凸包を計算したことになる．

図 8: ある円盤の中にランダムに分布した 10 万点の凸包を計算するためのイメージ．

２次元凸包を計算するこの方法は３次元凸包にそのまま拡張することができる．この場合，２次元凸包の計算での１次元的な帯は３次元凸包ではボロノイ図のような２として定義することができる．すなわち，与えられた母点次元的な模様となる．ドローネ三角形分割を計算するたのボロノイ図中で互いに隣り合う領域を作る２つの母点どめには，平面上に与えられた母点 (x, y) を３次元空間のうしをすべて結んだ平面グラフがドローネ三角形分割であ点 (x, y, x2 + y 2 ) へ射影し（放物面上への射影になっている．グラフィックスハードウェアを用いてボロノイ図のイる），これらの点の３次元凸包を計算して，凸包を構成すメージを得る場合には，いくつかの問題点が存在する．まる辺を２次元平面へ射影すれば，それがドローネ三角形分ず，ボロノイ図のイメージを得る場合には，無限に広い平割になっていることが知られている．したがって，３次元面全体のイメージを計算することは不可能であるため，あ凸包が計算できれば，それを用いてドローネ三角形分割をる限られた矩形内のイメージを得ているに過ぎない．従っ計算することは容易である．この方法を用いれば，ボロノて，この矩形内のイメージの情報からすべての隣接関係をイ図のイメージを直接調べるのとは異なり，すべての隣接見つけ出すことは原理的に不可能である．また，ボロノイ関係が得られる．

図のイメージはピクセルによって表現された離散的なもの

次に，２次元凸包の場合に膨大なピクセルから色の境界であり，連続的な情報を得ることができない．さらに，ピを見つけ出す方法について述べる．この方法は 3 次元凸包

クセルの個数は膨大であり，この１つずつをトレースするの場合にも拡張することができる．２次元の場合，直線状と，それだけで計算量が爆発することになる．これらの問にピクセルが並んでいるので，左から順にスキャンすれば題のいくつかは解決可能であり，また，残りのいくつかは境界を見つけることができる．しかし，この場合，ピクセある程度の制限の下で解決することができる．

ル数に比例する計算量が必要となり，高精度に問題を解こ

たとえば，隣接関係の問題は，ドローネ三角形分割の問うとした場合には計算量が爆発する．この場合，それぞれ題を 3 次元凸包の問題に置き換えることにより解決する．の色の領域は連結している．これは，３次元空間中に直線ここで述べてきたボロノイ図の描画の手法と本質的に同じを描画してある方向から見ていることから明らかである．

であるが，２次元および 3 次元凸包はグラフィックスハー

この性質を用いることによって，以下の再帰的アルゴリズ

ドウェアを用いて計算することができる．ここでは２次元ムによって，O(m log M ) ですべての境界を列挙することの凸包についての [11] の計算法の概略について述べる．

ができる [12]．ただし，m は凸包上の点の数であり，Mはピクセル数である．

平面上の n 点の２次元凸包とは，この n 点を含む最小の凸多角形のことである．この多角形を計算するというアルゴリズム 1 ([12]) 区間 [x, y] (0 ≤ x < y ≤ 1) の中ことは，この多角形を構成する頂点を順に列挙することとのすべての色の境界を列挙する関数 E(x, y).

同値である．ここで，与えられた点を通って傾き α の直線を考える．これらの直線のうちの２本は凸包の接線とな

1function E(x, y)

り，その y 軸との切片は，これらの直線の中でそれぞれ最2begin

小と最大になる．傾き α をある範囲で動かして考えれば，

3if c(ϕ(x)) = c(ϕ(y)) then return ∅切片はそれぞれ α の１次式として表現される．たとえば，

4else if ϕ(x) + 1 = ϕ(y) then

図 7 の左図では５つの点が平面上に置かれていて，凸包を5return {(c(ϕ(x)), c(ϕ(y)))}構成する点は A, B, C, D の 4 点である．ここで，傾き α6(−1 ≤ α ≤ 1) の直線を考える．それぞれの点を通過する
7直線の y 軸との切片は α の一次式として表現され，α を横4else ³return ´´³x+y [x+y,yE x,E
22end狭い領域に境界が多数集まることによって，本来は凸包のCPU一部なのにイメージ上に出現しない色が出てくる可能性がある．ここでは，出現しない色が発生しないくらい細かくvertex processor

描画が行われると仮定する．この仮定の下では常に正しい凸包が出力される．取り出した画像情報を利用する場合にGPUも，常に同様の問題が存在し，ある程度の細かさで画像を生成しない限り正しい情報を得ることができない．３次元凸包問題に関しても同様の問題が起こる．３次元凸包の場

rasterizer
fragment processor

合には，得られるパターンの中で３つの領域が隣り合う点を数え上げることが，３次元凸包の表面三角形を数え上げframe bufferることと同値である．実は３次元凸包の場合には，問題はさらに深く，いくら細かく見ても同じ領域の色が飛んだよ

screenうに見えるケースが存在する．飛んだ領域については，ある程度広い範囲で領域を見ることができれば数え上げるこ
図 9: グラフィックスハードウェアを構成する主なプロセッサ．とができるが，現実には画面上の描画できる領域の広さは限られており，正しい計算結果が得られない可能性がある．
しかし，ボロノイ点でそれほど多くない個数の領域（３領域でなくても良い）が接するケースでは，ある程度の精度大規模なボロノイ図をグラフィックスハードウェアで描でイメージを描画すれば問題なく３次元凸包が計算される．

く場合，フラグメントプロセッサに対する負荷は大変なものである．たとえば，1000 母点のボロノイ図を 600 × 600

4.のウィンドウに描画することを考えよう．それぞれの母点描画の効率について

について，360, 000 点のピクセルのすべてについて，それユークリッド平面上のボロノイ図を本稿で述べる方法

までに図形が描かれることによって変化した深さと，それで計算した場合，プログラムを作る手間は普通のアルゴリ

ぞれのピクセルに対応する深さバッファの値との比較を行ズムに比べて比較にならないほど小さい．また，どのようわなければならない．したがって，合計で 3.6 × 108 回のに計算すればよいかはっきりとしないボロノイ図でも定義比較演算が行われることになる．もちろんフラグメントプに従って描画することができる．一方，効率については，ロセッサはその内部にある複数のプロセッサによって並列必ずしも高いとはいえない．現在のグラフィックスハードに比較を行うが，その並列度には限界がある．したがって，ウェアの描画速度は非常に高速であり，その内部では部分現実にはボロノイ図はそれほど高速に描画できないことに的に並列に動作している．それにもかからず，大規模なボなる．

ロノイ図をここで述べるような方法でそのまま描画する場

ユークリッド平面上の通常のボロノイ図を考えたときに合，速いグラフィックスハードウェアを用いてもそれほどは，この状況を改善することができる．実際，描画面のあ高速に描画できるわけではない．

る部分を眺めたとき，ほとんどの面は一番上の幾つかの面

図 9 にグラフィックスハードウェアの大雑把なブロックによって隠されてしまう．したがって，フラグメントプロ

図を示す．図中で頂点プロセッサ (vertex processor) は，セッサによって扱われる情報のほとんどは描画に寄与して座標変換やクリッピングなど与えられた頂点情報に関すいない．もちろんどの面が表面に出てくるか否かは，実際る処理を行う部分である．CPU で計算された図形の情報に比較してみなければわからないということになるし，どは，まず，このプロセッサで処理されたあと，ラスタライの面もいずれかの位置にその色が出現するので，ある母点ザ (rasterizer) によってピクセル情報に変換される．このについて描画しないわけにはいかない．しかし，描画するピクセル情報 (それぞれのピクセルの色情報，深さ情報，場所に制限を加えた場合には状況が変わる．たとえば，山テクスチャマッピングの座標などが含まれる）に対し，フ本 [13] は，ボロノイの描画面をいくつかの小さな領域にラグメントプロセッサ (fragrment processor) によって隠分けて，それぞれの領域で出現する色をあらかじめ調べる

面処理や光源やテクスチャーに関する計算などが行われ，ことによって，ボロノイ図の描画が加速できることを示し実際に画面に表示される．

た．これは，図 9 のブロック図で見ると，描画の負荷をフ

グラフィックスハードウェアを用いてボロノイ図を描画

ラグメントプロセッサから頂点プロセッサや CPU に移しする場合，それぞれのピクセルに関する隠面処理の計算がていることに他ならない．この方法によって，描画速度が本質であって，この部分の機能が集中的に使われる．もち10 倍から 20 倍になることもある．この方法の性能は使用

ろん，頂点プロセッサによって，与えられた多角形の画面するグラフィックスハードウェアの構成や内部プロセッサ座標への変換などを計算する必要はあるが，フラグメントの速度比などによって色々に変化する．また，この手法はプロセッサに比べれば，負荷はそれほど重くない．

通常のボロノイ図ばかりではなく，色々なボロノイ図に適

5

[4] Hoff, K. E., Culver, T., Keyser, J., Lin, M.,

用できると考えられるが，これは今後の課題である．

and Manocha, D.: Fast computation of general5.

ized Voronoi diagrams using graphics hardware. In

おわりに

Proceedings of ACM SIGGRAPH Annual Confer-

本稿ではグラフィックスハードウェアを用いた各種ボロ

ence on Computer Graphics, ACM, (1999) 277–286

ノイ図の描画方法およびその周辺の話題について述べた．

[5] Kilgard, M. J.: OpenGL Programming for the X

グラフィックスハードウェアは CPU とは別のハードウェ

Window System. Addison-Wesley. (1996)

アであり，画像を描画するためのいくつかの特殊な演算に[6] Ohya, T., Iri, M., and Murota, K.:

関しては非常に高速に動作する．その内部では，いくつかIm-provement of incremental method for Voronoi di-のプロセッサがパイプライン状に連結され，並列に動作す

agram with computational comparison of algo-る．また，画面のピクセルに対応する色，深さ，およびそのrithms. Journal of Operations Research Society of

他の情報を蓄えるためのメモリを持っている．これは，ソJapan 27, (1985) 306–336

フトウェアの立場からみれば，巨大な２元配列とその配列[7] Okabe, A., Boots, B., and Sugihara, K.: Spa-を高速に操作するための専用ハードウェアがセットになっtial Tessellations – Concepts and Applications ofたものと考えることができる．それぞれの操作は高速に動Voronoi Diagrams. John-Willey. (1992)

作するが，その機能を目的とする計算にうまく合わせるこ[8] Rost, R. J.: OpenGL Shading Language, Addisonとは，それぞれの演算が図形の描画に特化されていること

Wesley. (2004)

からそれほど容易ではない．現在では，グラフィックスハー
ドウェア内部の頂点プロセッサやフラグメントプロセッサ[9] Shamos, M. I., and Hoey, D.:

Closest-pointなどについては，特殊なプログラムを与えることによってproblems. In Proceedings of Annual IEEE Sympo-

その動作を変更させることが可能になっている [2, 8]．単

sium on Foundation of Computer Science, IEEE,にボロノイ図を描画するためには，現在のところ，このよ(1975) 151–162

うな機能を用いる必要はないが，より高度な計算をさせる[10] Woo, M., Neider, J., Davis, T., and Shreiner,

ために，今後検討して行く必要があると考えられる．

D.: OpenGL Programming Guide, third edition ed.

ボロノイ図を画面に描画することだけが目的であれば，Addison Wesley. (1999)

適当な図形を描画すれば良い．その画像データを別の計算[11] Yamamoto, O.: Fast display of Voronoi diagramsに利用するためには，得られたデータの質に関する保証がover planes and spheres using graphics hardware.

必要となる．狭い場所に多くの母点やボロノイ点が集中しTransactions of the Japan Society for Industrial

たようなボロノイ図のイメージは，利用法にもよるが，情and Applied Mathematics 12, 3, (2002) 209–234

報としては不完全である．通常のアルゴリズムでは，退化(in Japanese)の発生問題などについて，記号摂動法 [1, 14] などを利用[12] Yamamoto,することにより解決することができるが，グラフィックス

O.:

Fast computation of 3-

ハードウェアで画像を描画する場合には，退化が起こらな

dimensional convex hulls using graphics hard-

い代わりに，ピクセルを見たときに前述のような「飛んだware.

点」が発生する可能性がある．この問題の現実的な解決は，

on Voronoi Diagrams in Science and Engineering,今後の課題である．

September 13-15, 2004, Tokyo, Japan, (2004) 179–

Proceedings of International Symposium

190[13] Yamamoto, O.:

参考文献

An acceleration technique forthe computation of Voronoi diagrams using graph[1] Edelsbrunner, H., and Mucke, E. 1988. Sim-ics hardware. Proceedings of International Confer-ulation of simplicity – a technique to cope withence on Computation Science and its Applications,degenerate cases in geometric algorithms. In Pro-2005, O. Gervasi et al. (Eds.), May 9-12, 2005, Sin-ceedings of the 4th ACM Annual Symposium ongapore, Tokyo, Japan, Lecture Notes in Computer

Computational Geometry, ACM, 118–133

Science vol. 3480, Springer-Verlag, Berlin, Heidelberg, (2005) 786–795[2] Fernando, R. GPU Gems: Programming Tech-[14] Yap, C.-K. 1988. A geometric consistency theo-niques, Tips, and Tricks for Real-Time Graphics

rem for a symbolic perturbation scheme. In Pro-

Addison-Wesley. (2004)

ceedings of 4th ACM Annual Symposium on Com-

[3] Fortune, S.: A sweepline algorithm for Voronoi

putational Geometry, ACM, 134–142

diagrams. Algorithmica 2 , (1987) 153–174

6