Триангуляция Делоне. Полигоны Вороного

Задача построения триангуляции Делоне является одной из базовых в вычислительной геометрии. К ней сводятся многие другие задачи, она широко используется в машинной графике и геоинформационных системах для моделирования поверхностей и решения пространственных задач. Впервые задача построения триангуляции Делоне была поставлена в 1934 г. в работе советского математика Бориса Николаевича Делоне.

Введение 3
1.Триангуляция Делоне
1.Основные определения и задачи триангуляции Делоне 4
2.Теоремы для алгоритмов построения триангуляции Делоне 6
3.Структуры для представления триангуляции 7
1.Структура «Узлы с соседями» 7
2.Структура «Двойные ребра» 8
3.Структура «Узлы и треугольники» 9
4.Структура «Узлы, ребра и треугольники» 10
5.Структура «Узлы, простые ребра и треугольники» 10
2.Алгоритмы триангуляции Делоне
1.Классификация алгоритмов триангуляции Делоне 12
2.Итеративные алгоритмы с кэшированием поиска треугольников 13
1.Алгоритм со статистическим кэшированием поиска 13
2.Алгоритм с динамическим кэшированием поиска 14
3.Полигоны Вороного 15
Заключение 16
Список использованной литературы 17