３次元でのドロネー三角化とボロネイ多面体化

• 平面に点を撒いて、そこに三角形埋め尽くしを作る方法にドロネー三角化があり、その双対としてボロノイ図がある。ボロノイ図では多角形充填が得られる
• その3次元版もあって、3次元空間に点を撒いて、四面体で空間を分割する。その双対がボロノイ分割で、それは多面体充填分割になる
• ボロノイ多面体の境界は、撒いた点を結ぶ線分の垂直二等分面で構成される。１つの四面体の６つの辺の垂直二等分面は1点で交わる(四面体の外心)が、その点から、四面体４頂点までの距離は等しい。ボロノイ多面体をグラフとして描くと、隣り合うドロネー四面体の外心同士を結んだものとなる
• 四面体は必ず４つの四面体と隣り合うから、このボロノイ多面体グラフは４正則グラフになる(周囲を除く)