Реферат Геометричний пошук Означення. Пошукове повідомлення, у відповідності з яким ведеться перегляд файла, називається запитом. Нехай є


СкачатиСкачать (DOC|ZIP):
Геометричний пошук Означення. Пошукове повідомлення, у відп

Реферат на тему:

Геометричний пошук

Означення. Пошукове повідомлення, у відповідності з яким ведеться перегляд файла, називається запитом.

Нехай є набір геометричних даних і треба встановити, чи мають вони певну властивість. Якщо запит виникає один раз, то його будемо називати унікальним. Запити, обробка яких повторюється декілька разів в одному і тому ж файлі, називаються масовими.

Міри оцінки запиту:

1. Час запиту. Скільки часу необхідно в середньому, у найкращому та найгіршому випадках.

2. Пам’ять. Скільки пам’яті необхідно для зберігання структури даних.

3. Час передобробки. Скільки часу необхідно для організації даних перед пошуком.

4. Час корегування. Дано елемент даних. Який час необхідно використати на його видалення чи вставку до структури даних.

Означення. Передобробкою будемо називати процес розташування даних у зручній для подальшої обробки структурі даних.

Задача. Геометричний пошук. Дано планарний граф G з N вершинами та точка z. Необхідно встановити область графу G, в якій розташована точка z.

Час передобробки не може бути меншим за O(N), оскільки навіть процес читання вершин вимагає час O(N). Витрати по пам’яті не можуть бути меншими за O(N) при зберіганні у довільній структурі даних, оскільки навіть для зберігання самого графа G вимагаються витрати по пам’яті O(N). Запит до структури даних, яка містить N елементів, вимагає як мінімум часу O(N * log N).

Регіональний пошук

Задача. Регіональний пошук. Дано N точок на площині. Скільки точок лежить всередині заданого прямокутника, сторони якого паралельні координатним осям? Тобто скільки точок (x, y) задовольняє нерівностям a ≤ x ≤ b, c ≤ y ≤ d для заданих a, b, c, d?

Метод локусів. (Локус – це застарілий термін “геометричне місце точок”). Запиту ставиться у відповідність точка у зручному для пошуку просторі, а цей простір розбивається на області (локуси), в межах яких відповідь не змінюється.

Означення. Точка (вектор) v домінує над w тоді і тільки тоді коли для усіх індексів i справедлива умова vi ≥ wi.

Q(P1) = 14, Q(P2) = 9, Q(P3) = 1, Q(P4) = 2. N(P1P2P3P4) = 14 - 9 - 2 + 1 = 4

На площині точка v домінує над w тоді і тільки тоді коли w лежить у лівому нижньому квадранті, що визначається v. Позначимо через Q(p) кількість точок, над якими домінує p. Кількість точок N(p1p2p3p4) у прямокутнику p1p2p3p4 визначається наступним чином:

N(p1p2p3p4) = Q(p1) - Q(p2) - Q(p4) + Q(p3)

Задачу регіонального пошуку зведено до задачі обробки запитів про домінування для чотирьох точок. Опустимо із заданих точок на вісі x та y перпендикуляри, а отримані лінії продовжимо у нескінченність. Утворилася решітка з (N + 1)2 прямокутників.

Теорема. Часови оцінки запропонованого алгоритму: пердобробка – O(N2), пам’ять – O(N2), запит – O(log N).

Задачі локалізації точки

Задача. Належність точки простому многокутнику. Дано простий многокутник (N - кутник) P та точка z. Чи знаходиться точка z в середині P?

Алгоритм. Проведемо через точку z горизонталь l. Якщо l не перетинає P, то z – зовнішня точка. Припустимо, що l перетинає P та не проходить через жодну його вершину. Нехай L – кількість точок перетину прямої l з границею P зліва від z. Очевидно, що точка z лежить всередині многокутника тоді і тільки тоді, коли L непарне.

Якщо пряма проходить через вершини многокутника, то при обчисленні значення L необхідно користуватися наступними правилами: якщо обидві вершини ребра належать l, то це ребро треба відкинути; якщо тільки одна вершина ребра лежить на l, то перетин враховується, якщо це вершина з більшою ординатою та ігнорується інакше.

Належність простому многокутнику

begin

L ← 0;

for i ← 1 to N do

if ( ребро ( i ) не горизонтальне) then

if ( ребро( i ) перетинає l нижнім кінцем зліва від z)

then L ← L + 1;

if (L непарне) then z всередині else z ззовні;

end.

Теорема. Належність точки z внутрішній області простого N - кутника можна встановити за час O(N) без передобробки.

Задача. Належність точки опуклому многокутнику. Дано опуклий многокутник (N - кутник) P та точка z. Чи знаходиться точка z в середині P?

Алгоритм. Вершини опуклого многокутника впорядкуємо за полярними кутами відносно довільної внутрішньої точки q, в якості якої можна взяти, наприклад, центр ваги довільних трьох вершин P. Проведемо N променів з точки q через вершини многокутника. Ці промені розіб’ють площину на N клинів, кожен з яких розбивається стороною многокутника на дві частини. За допомогою двійкового пошуку можна знайти клин, в якому лежить точка z (промені розташовані в порядку зростання їх полярних кутів проти годинникової стрілки). Точка z лежить між променіми pi та pi+1 тоді і тільки тоді, коли кут (zqpi+1) додатний, а кут (zqpi) від’ємний. Коли точки pi та pi+1 знайдено, то точка z буде внутрішньою тоді і тільки тоді, коли кут (pipi+1z) від’ємний.

Теорема. Час відповіді на запит про належність точки опуклому N - кутнику дорівнює O(log N) при затраті O(N) пам’яті та O(N) часу на попередню обробку.

Попередня обробка полягає в розташуванні вершин многокутника в структурі даних, придатної для двійкового пошуку.

Зірчасті многокутники є більш обширним класом простих многокутників, що включають в себе опуклі многокутники. Зірчастий многокутник містить хоча б одну таку точку q, що відрізок qpi повністю лежить всередині многокутника P для довільної вершини pi. Множина всіх можливих таких точок q називається ядром P. Після знаходження такої точки q можна використовувати попередній алгоритм.


СкачатиСкачати: Геометричний пошук Означення. Пошукове повідомлення, у відп


Схожі реферати:
  • Місто Київ – економічний потенціал району
  • Виконання спеціального завдання з попередження чи розкриття злочинної діяльності організованої групи чи злочинної організаці
  • КУРСОВА РОБОТА на тему: Складання й оформлення службових документів ЗМІСТ 1. Організаційно-правові документи 2. Розпорядчі документи. Накази з осн
  • Слов'янська міфологія (реферат)
  • РЕФЕРАТ на тему: Наука геронтологія ПЛАН 1. Поняття про геронтологію як науку 2. Поняття про тривалість життя, чинники тривалості життя 3. Стар
  • Працездатність і методи її підвищення Підвищення працездатності людини є одним із важливих факторів раціоналізації трудової діяльності. Ефективні
  • Роль бюджету в збалансованому розвитку національної економіки (реферат)
  • Ринок фінансових інформаційних послуг (курсова)
  • Проектування організаційної структури управління, суть, принципи, етапи (реферат)
  • Інвестиційна діяльність населення Фінанси населення за джерелами формування належать до сфери споживання, але завжди від споживання у населення залиш




  • Скористайтеся пошуком:
    Loading

    Пошук :

    0.034458