ドロネー図
提供: miniwiki
ファイル:Delaunay Triangulation (100 Points).svg
.svg){kind=link}
ドロネー三角形分割の一例
ドロネー図（ドロネーず、英語：Delaunay diagram）あるいはドロネー三角形分割（ドロネーさんかっけいぶんかつ、露: триангуляция Делоне, 英: Delaunay triangulation）は、距離空間内に離散的に分布した点の集合に対し得られる、それらをある方法に従い辺で結んだ図形である。
計算幾何学あるいは離散幾何学における代表的な考察対象の1つである。名称は考案者であるロシアの数学者、ボリス・ドロネー（露: Борис Николаевич Делоне）に由来する。ドロネー図の双対はボロノイ図であり、ドロネー図はボロノイ領域の隣接関係を表している。
双対
与えられたボロノイ図から対応するドロネー図を作図するには、与えられたボロノイ図の各領域（ボロノイ領域）に一つずつの特定の点（母点）を選んで固定し、どの二つのボロノイ領域についても、それが隣接ボロノイ領域ならば母点同士を結び、隣接していない場合は二つの母点を結ばないという操作を行う。元のボロノイ図の母点をドロネー点、得られたドロネー図のドロネー点を結んでいる線分をドロネー辺あるいはドロネー境界という。二次元のドロネー図ならば、ドロネー点とドロネー辺は多角形（ドロネー多角形）をつくるが、特殊な場合を除きこの多角形は三角形となり（退化して三角形とならない場合には母点を取り替えることで解消できる）、平面はドロネー図によってドロネー三角形の集まりに分割される。これをドロネー三角形分割という。次元を上げても同様のこと（ドロネー単体分割）を考察することができる。