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

Задача. Дано множину 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).
Случайные рефераты:
Реферати - Любовна лірика Ліни Костенко
Реферати - Аналіз повісті "Кайдашева сім’я" Івана Нечуя-Левицького
Реферати - Естетична функція кольору в романах Павла Загребельного
Реферати - Жанрова своєрідність творів О.Вишні
Реферати - Життя та творчість Василя Барки
Реферати - Дитяча Література (контрольна робота)
Реферати
  • Всі реферати
  • Архітектура
  • Астрономія, авіація
  • Аудит
  • Банківська справа
  • Безпека життєдіяльності
  • Біографія, автобіографія
  • Біологія
  • Бухгалтерський облік
  • Військова кафедра
  • Географія
  • Геологія
  • Гроші і кредит
  • Державне регулювання
  • Діловодство
  • Екологія
  • Економіка підприємства
  • Економічна теорія
  • Журналістика
  • Іноземні мови
  • Інформатика, програмування
  • Історія всесвітня
  • Історія України
  • Історія економічних вчень
  • Краєзнавство
  • Кулінарія
  • Культура
  • Література
  • Макроекономіка
  • Маркетинг
  • Математика
  • Медицина та здоров'я
  • Менеджмент
  • Міжнародні відносини
  • Мікроекономіка
  • Мовознавство
  • Педагогіка
  • Підприємництво
  • Політологія
  • Право
  • Релігієзнавство
  • Промисловість
  • Сільське господарство
  • Сочинения на русском
  • Соціологія
  • Литература на русском
  • Страхування
  • Твори
  • Фізика
  • Фізична культура
  • Філософія
  • Фінанси
  • Хімія
  • Цінні папери
  • Логіка
  • Туризм
  • Психологія