Триангуляция

Реферат на тему:
Триангуляция
Определение. Алгоритм называется жадным, если на одном шаге не отменяется то, что уже было сделано.
Задача. Дано множество S из N точек. Построить триангуляции множества S.
Жадный Триангуляция
Порождается множество K с n * (n — 1) / 2 ребер, соединяющих точки множества S, и упорядочивается по возрастанию их длин. Далее из множества K выбирается ребро с наименьшим длиной. Если это ребро не пересекает ни одно из ребер, которые вошли в триангуляции, то оно включается в триангуляции. Иначе ребро исключается из дальнейшего рассмотрения. Процесс закончится или когда Триангуляция уже построена (это можно определить подсчитывая количество ребер в триангуляции), или когда все ребра множества K будут рассмотрены.
Сортировка ребер по длине требует O (N2 log N) операций. Затем исследуется O (N2) ребер множества K на проверку пересечения с ребрами триангуляции. Такая проверка для каждого ребра множества K может потребовать время O (N). Итак полное время обработки составляет O (N3).
Подход Джильбертом принятия решения.
Предположим, что текущим ребром, выбранным из множества K, является p1pi.
гражданство мальты за инвестиции

Рассмотрим множество ребер, соединяющих p1 с другими точкамимножины S и обозначим его ЗВЕЗДА (p1). Лучи звезды упорядочены в порядке обхода вокруг точки p1 и делят полный угол на N — 1 угловых интервалов (секторов). Если некоторое ребро pkpj включен в триангуляции, то оно проходит через несколько последовательных секторов звезды с центром p1. Поскольку ребра, включенные в триангуляции, не пересекаются, то ребра в каждом секторе можно считать отсортированными. Предположим что точка pi попала в сектор pjp1pk с ЗВЕЗДА (p1). Для решения вопроса о занесении ребра p1pi к триангуляции следует определить, пересекает оно ребра триангуляции указанного сектора (даже не все ребра сектора, а только ближе к p1 ребро). Задача приятно свелась к частичному случае задачи определения положения точки на плоскости. В каждом секторе, определяется ЗВЕЗДА (p1), необходимо хранить ближе всего к p1 (опорное) ребро.
Теорема. Триангуляция множества из N точек жадным алгоритмом может быть построена за время O (N2 log N) с использованием памяти O (N2).

Комментирование и размещение ссылок запрещено.

Комментарии закрыты.