Обзор алгоритмов построения триангуляции Делоне
Скворцов А.В.

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

Скворцов А.В. - Томский государственный университет, факультет информатики, пр. Ленина, д. 36, 634050, г. Томск, e-mail: skv@csd.tsu.ru