ボロノイ図

Theme

ボロノイ図とは，「ある範囲内の母点の集合で，その他の点がどの母点に近いかによって領域分けされた点」をいう．

    • 定義
    • 2等分線Bis(p_i,p_j)=\{x|d(p_i,x)=d(p_j,x)\}
    • により2つの半平面に分離したものをそれぞれ
    • H(p_i,p_j)，H(p_j,p_i)としたとき，
    • 母点集合Sに関するボロノイ領域は，
      • VoR(p_i,S)=\bigcap_{p_j\in S, p_j\neq p_i}H(p_i,p_j)
    • S自身のボロノイ図VD(S)は，
      • VD(S):=\bigcup_{p_i,p_j\in S, p_i\neq p_j}(\overline{VoR(p_i,S)}\cap \overline{VoR(p_j,S)})
  • ボロノイ図はグラフを表す
    • ボロノイ辺：2つのボロノイ領域が共有する領域
    • ボロノイ点：ボロノイ辺の端点(3つのボロノイ領域の共通境界に属する)
    • 「ドロネー三角形分割」はボロノイ図の双対グラフ
  • 応用例
    • 画像処理
      • 圧縮
      • モザイク
      • 隣接補完
    • 離散データの集約
    • 郵便配達問題
    • 基地局配置(センサノード配置)
    • など