В работе рассматриваются многие известные алгоритмы построения триангуляции Делоне и предлагается их классификация. Для всех алгоритмов приводится оценка их трудоемкости в среднем и худшем случаях. Обсуждаются особенности реализации. Рассматриваются четыре структуры данных для представления триангуляции. Приводятся процедуры проверки условия Делоне и описываются процедуры слияния триангуляции.

обчислювальна геометрія, вычислительная геометрия