Показать сообщение отдельно
  #1  
Старый 15.05.2010, 23:11
гость

 
Сообщений: n/a

Dalaunay Triangulation
Доброго времени суток,

Есть такая проблемка. Задан планарный граф (вершины + некоторые ребра). Нужно проверить возможность построения триангуляции Делоне (заданые ребра обязательно должны быть ребрами триангуляции). Сложность алгоритма в худшем случае порядка N^2 от количества вершин. Помогите с идейкой.

Заранее благодарен.