ドロネー三角形分割

この条件を示したのはボリス・ドロネーで、1934年のことである。点集合の三角形分割は無数にあるが、ドロネー分割は細長い「スリバー」三角形をできるだけ避ける。空の外接円という条件が、三角形の形を可能な限り整えるからだ。ボロノイ図の幾何学的な双対でもある。

ゲームやグラフィックスでは、高さデータから作る地形（TIN）、品質の良いメッシュの生成、ナビメッシュの基礎などに使われる。代表的なアルゴリズムはBowyer–Watson法（逐次的な外接円判定）と分割統治法。イヤークリッピングが単に面を三角形に分けることだけを目的とするのに対し、こちらは三角形の質まで問題にする。