Триангуляція
Означення. Алгоритм називається жадним, якщо на жодному кроці не відміняється те, що вже було зроблено.

Задача. Дано множину S з N точок. Побудувати триангуляцію множини S.

Жадібна триангуляція

Породжується множина K з n * (n - 1) / 2 ребер, що сполучають точки множини S, та впорядковується за зростанням їх довжин. Далі з множини K вибирається ребро з найменшою довжиною. Якщо це ребро не перетинає жодне з ребер, які увійшли до триангуляції, то воно включається до триангуляції. Інакше ребро виключається з подальшого розглядання. Процес закінчиться або коли триангуляція вже побудована (це можна визначити підраховуючи кількість ребер у триангуляції), або коли всі ребра множини K будуть розглянуті.

Сортування ребер по довжині вимагає O(N2 log N) операцій. Потім досліджується O(N2) ребер множини K на перевірку перетинання з ребрами триангуляції. Така перевірка для кожного ребра множини K може вимагати час O(N). Отже повний час обробки дорівнює O(N3).

pk

pi

pj

p1

Підхід Джільберта прийняття рішення.

Припустимо, що поточним ребром, обраним з множини K, є p1pi. Розглянемо множину ребер, які сполучають p1 з іншими точками множини S та позначимо його ЗІРКА(p1). Проміні зірки впорядковані у порядку обхода навколо точки p1 та ділять повний кут на N - 1 кутових інтервалів (секторів). Якщо деяке ребро pkpj включене до триангуляції, то воно проходить через декілька послідовних секторів зірки з центром p1. Оскільки ребра, включені до триангуляції, не перетинаються, то ребра у кожному секторі можна вважати відсортованими. Припустимо що точка pi попала до сектора pjp1pk із ЗІРКА(p1). Для вирішення питання про занесення ребра p1pi до триангуляції слід визначити, чи перетинає воно ребра триангуляції вказаного сектора (навіть не всі ребра сектора, а лише найближче до p1 ребро). Задача перетину звелася до часткового випадку задачі визначення положення точки на площині. В кожному секторі, що визначається ЗІРКА(p1), необхідно зберігати найближче до p1 (опорне) ребро.

Теорема. Триангуляція множини з N точок жадним алгоритмом може бути побудована за час O(N2 log N) з використанням пам'яті O(N2).
Случайные рефераты:
Реферати - Життєвий і творчий шлях Юрія Федьковича
Реферати - Олексій Коломієць
Реферати - Образ Пузиря за п 'єсою "Хазяїн" Івана Карпенка-Карого
Реферати - Мотиви драматичної спадщени Миколи Куліша
Реферати - Дмитро Білоус
Реферати - Літературний подвиг Тараса Григоровича Шевченка
Реферати
  • Всі реферати
  • Архітектура
  • Астрономія, авіація
  • Аудит
  • Банківська справа
  • Безпека життєдіяльності
  • Біографія, автобіографія
  • Біологія
  • Бухгалтерський облік
  • Військова кафедра
  • Географія
  • Геологія
  • Гроші і кредит
  • Державне регулювання
  • Діловодство
  • Екологія
  • Економіка підприємства
  • Економічна теорія
  • Журналістика
  • Іноземні мови
  • Інформатика, програмування
  • Історія всесвітня
  • Історія України
  • Історія економічних вчень
  • Краєзнавство
  • Кулінарія
  • Культура
  • Література
  • Макроекономіка
  • Маркетинг
  • Математика
  • Медицина та здоров'я
  • Менеджмент
  • Міжнародні відносини
  • Мікроекономіка
  • Мовознавство
  • Педагогіка
  • Підприємництво
  • Політологія
  • Право
  • Релігієзнавство
  • Промисловість
  • Сільське господарство
  • Сочинения на русском
  • Соціологія
  • Литература на русском
  • Страхування
  • Твори
  • Фізика
  • Фізична культура
  • Філософія
  • Фінанси
  • Хімія
  • Цінні папери
  • Логіка
  • Туризм
  • Психологія