Триангуляция Делоне

Триангуля́ция Делоне́ (Delaunay triangulation) — связный плоский граф с множеством точек на плоскости [math]\displaystyle{ S }[/math] в качестве вершин, каждая внутренняя грань которого является таким треугольником, что все точки из [math]\displaystyle{ S }[/math] (за исключением точек, являющихся вершинами треугольника) лежат вне окружности, описанной вокруг данного треугольника. Впервые описана в 1934 году советским математиком Борисом Делоне.