Локалізація точки

ППЛГ розбивається на смуги.

Через кожну вершину графу проводимо вертикальну лінію. Таким чином отримуємо вертикальні смуги впорядковані за координатою x. Для кожного ребра, яке перетинає смугу записуємо нове укорочене ребро у впорядкований перелік за координатою y. Пошук відбувається за логарифмічний час з використанням квадратичної пам'яті у найгіршому випадку.

ППЛГ з деякими розфарбованими монотонними ланцюгами.

Ідея методу походить від пошуку в прямокутній решітці. Граф розбивається на «вертикальні» та «горизонтальні» смуги. В методі ланцюгів вертикальні смуги замінюються на ланцюги монотонні відносно осі Oy. При запиті відносно розташування точки в ППЛГ, спочатку відбувається бінарний пошук для з'ясування між якими «вертикальними» ланцюгами розташована точка. Такий пошук реалізується за допомогою підпрограми, яка обробляє запит (ланцюг, точка) і дає відповідь на те, як розташована точка відносно ланцюга — ліворуч чи праворуч.

Алгоритм який з'ясовує розташування точки працює за допомогою бінарного пошуку. Тим самим він працює з логарифмічною швидкістю.

У підсумку пошук відбувається за час ${\displaystyle \log ^{2}N}$. Використовується пам'ять ${\displaystyle N\log N}$.

Послідовні кроки методу уточнення триангуляції.

Багатокутник з m вершинами можна розбити на m-2 трикутника. Існують чисельні алгоритми для ефективної триангуляції багатокутника, найшвидший з них працює за час O(n) в найгіршому випадку. Таким чином, ми можемо розкласти кожен багатокутник нашого розбиття на трикутники, і обмежитися структурними даними на випадок розбиттів, сформованих виключно з трикутників. Kirkpatrick описує структуру даних для опису тріангульованого розбиття яка використовує пам'ять O(n) і запити виконуються за час O(log n).

Загальна ідея полягає у створенні ієрархії трикутників. Щоб виконати запит, ми почнемо з знаходження верхнього рівня трикутник, що містить точку запиту. Так як число трикутників верхнього рівня обмежено константою, ця операція може бути виконана за O(1). Кожен трикутник має вказівник на трикутники, які він перетинає в наступному рівні ієрархії, а кількість вказівників також обмежена константою. Переходимо із запитом на знаходження, який трикутник містить вказівник рівня запиту по рівню.

Структура даних побудована в зворотному порядку, тобто знизу вгору. Починаємо з тріангульованих підрозділів і вибираємо незалежний набір вершин, які будуть видалені. Після видалення вершин, ми ретріангулюємо підрозділ. Оскільки підрозділ формується з трикутників, жадібний алгоритм може знайти незалежний набір, що містить постійну частину вершин. Таким чином, кількість кроків видалення становить O(log n).

Трапецієподібне розкладання.

Увипадковлений підхід до задачі локалізації точки, і, ймовірно, найбільш практичний, заснований на трапецієподібному розкладанні або трапецієподібній карті. Трапецієподібне розкладання отримують, випускаючи вертикальні промені, що йдуть вгору і вниз з кожної вершини у вихідні підрозділи. Промені треба зупинити, коли вони потрапили в край, і сформувати новий край у підрозділі. Таким чином, ми отримаємо підмножину, яка є розкладанням в плиту, тільки з O(n) ребер і вершин, так як ми тільки додати два ребра і дві вершини для кожної вершини в первинному підрозділі.

Однак, це не легко побачити, як використовувати трапецієподібне розкладання для точки розташування, так як бінарний пошук, аналогічний використовуваному в плитковому розкладанні не може бути більше використаний. Замість цього, нам необхідно відповісти на запит у той же спосіб, як у уточненому підході тріангуляції, але структура даних будується зверху вниз. Спочатку ми будуємо трапецієподібне розкладання, яке містить лише рамку, і ніякої внутрішньої вершини. Потім ми додаємо сегменти з підрозділу, один за іншим, у випадковому порядку, уточнення трапецієподібного розкладання. Використання зворотного аналізу, ми можемо показати, що очікуване число трапецій, створених для кожної вставки обмежене константою.

Ми будуємо орієнтований ациклічний граф, в якому вершини є трапеції, які існували в якийсь момент в уточненні, і спрямовані ребра з'єднують трапеції отримані за допомогою підрозділів. Очікується, глибина пошуку в цьому орієнтованому графі, починаючи з вершини, яка відповідає прямокутнику, є O(log n).