Реферат на тему:
Триангуляція
Означення. Алгоритм називається жадним, якщо на жодному кроці не
відміняється те, що вже було зроблено.
Задача. Дано множину 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).
pk
pi
pj
p1
Нашли опечатку? Выделите и нажмите CTRL+Enter
