Improving Worst Case Optimal Delauney Triangulation Algorith

improving-worst-case-optimal-delauney-triangulation-algorith.png

登場人物

$D(S)$…三角形分割。m個の三角形を持っているらしい。その三角形の辺は$e$と呼ばれる。点$p_i$と点$p_j$を結ぶ辺は$\overline{p_{i}p_{j}}$と表現する。サイト$S$のデローニー三角形分割

特殊な用語

サイト…点のことみたい
plane sweep algorithm…平面走査アルゴリズム。

2つのボロノイ図作成法

Guibasのアルゴリズム

再帰的に分割する方法。分割したものを後でマージするらしい。

  1. 点をソートする。x座標、y座標で。
  2. 最初に左右2つに領域を分ける $L$,$R$と呼ぶことにする。

彼らは外接円の中に点が含まれているかどうかについて改良したらしい。

Fortuneのアルゴリズム

Fortunes-algorithm.gif
Fortuneのアルゴリズムの可視化←きれい!でわかりやすい。
平面をスイープしながらそこにある点を基準とした放物線を描く。
他の放物線と交差する点を次々と描いていくとボロノイ図の完成みたい。

サポートサイト Wikidot.com