Триангуляция Делоне
Триангуляция, максимизирующая наименьший угол: внутри окружности, описанной вокруг любого треугольника, нет других точек.
Борис Делоне сформулировал условие в 1934 году. Из всех способов разбить набор точек на треугольники Делоне выбирает тот, где нет длинных тонких «сливеров»: условие пустой окружности заставляет треугольники быть как можно более правильными. Это геометрически двойственный объект к диаграмме Вороного.
В играх и графике её применяют для рельефа (TIN-модели по данным высот), для построения качественных сеток и как основу навмешей. Типичные алгоритмы — Боуайера–Ватсона (инкрементальные проверки окружностей) и «разделяй и властвуй». В отличие от ear clipping, здесь важно не просто разрезать область на треугольники, а качество этих треугольников.