3.3.4. Метод трапецій
Означення 3.12 Дано два ребра e1 та e2 з E. Запис e1 < e2 означає, що існує горизонталь, яка перетинає обидва ребра, і точка її перетину з e1 знаходиться лівіше за точку перетину з e2.
Механізм побудови структури даних пошуку обробляє по одній трапеції та намагається розбити її на максимально можливу кількість менших трапецій. Це відбувається шляхом розрізання трапеції R на нижню R1 та верхню R2 горизонтальною прямою, яка є медіаною множини ординат вершин всередині R.
Означення 3.13 Якщо ребро графа G перетинає обидві горизонтальні сторони трапеції, то воно називається закриваючим.
Після визначення медіани ymed трапеції R множина ребер графа G, яка перетинає R, проглядається зліва направо та розділяється на дві множини, що відносяться до R1 та R2 (мал. 3.17). Якщо зустрічається закриваюче ребро, воно стає правою боковою границею нової трапеції, яка обробляється незалежно.
Розбиття трапеції. Кожній трапеції R відповідає дерево бінарного пошуку T(R), з лінійною перевіркою кожного вузла, які можуть бути двох типів: 
- вузли, що відповідають перевірці по горизонталі, та О - вузли, що відповідають перевірці відносно прямої, яка містить ребро графа (мал. 3.18).
Мал. 3.17
Корінь завжди є - вузлом. Кількість - вузлів у дереві пошуку = N - 2.
Мал. 3.18.Дерево пошуку
Алгоритм
В алгоритмі виділяються три основні дії:
- визначення медіани множини ординат вершин в R;
- розбиття нижнього і верхнього ярусів на трапеції і отримання для кожного яруса Ri (i= 1, 2) ланцюга Ui, який складається з ребер та дерев;
- балансування двох ланцюгів U1 та U2.
Процедура БАЛАНС потребує O(h log h) часу: розділення U - O(h) часу, два рекурсивних виклики процедури, які застосовуються до половин вихідного ланцюга.
Аналіз висоти збалансованих дерев. h < N, h - число дерев в ланцюзі U і нових трапецій, N - число вершин графа. Якщо многокутник має s вершин, то в ньому 
s - 3 діагоналей. Оскільки s N, то h s - 2 N - 2.
Теорема 3.12. Для заданого ланцюга U = Т1е1 ... еh-1Th висота d(U) дерева, побудованого за допомогою процедури БАЛАНС, не перевищує 
.
Для плоского прямолінійного графа справедлива нерівність W(U) N 
висота дерева пошуку для графа не перевищує 
.
Теорема 3.13. Точку можна локалізувати в N-вершинному планарному підрозбитті методом трапецій менше ніж за 4 log2 N перевірок, з використанням O(N log N) пам'яті і такого ж часу попередньої обробки.
function TРАПЕЦІЯ (E, V, I)
begin if (V = Ø) then return L (*листок дерева пошуку*)
else begin E1:= E2:= V1:= V2:= U:= Ø;
ymed:= медіана множини ординат V;
I1:= [min (I), ymed]; I2:= [ymed, max (I)];
repeat e
E;
for i = 1,2 do
begin if (e має кінець p всередині Ri)
then
begin E
i e;
V
i:= V
i 
{p}
end;
if (e накриває Ri)
then begin U
i ТРАПЕЦІЯ(E
i, V
i, I
i);
if (e
L )
then U
i e;
Ei:= Vi:= Ø
end
end
until e = L;
новий (w); (*створення нового вузла w, кореня T(R)*)
Y[w]:= ymed; (*дискримінація вузла w*)
ЛДЕРЕВО[w]:= БАЛАНС(U1);
ПДЕРЕВО[w]:= БАЛАНС(U2);
(*ф-ція БАЛАНС приймає на вході послідовність із
дерев та ребер і організовує їх в збалансване дерево*)
return ДЕРЕВО[w]
end
end.
Вершини трапеції розташовуються в масиві за зростанням ординат. Модифікація процедури ТРАПЕЦІЯ проходить наступним чином. Послідовність ребер проглядається двічі. При першому проході кожна вершина просто помічається іменем тієї трапеції, до якої вона належить, будується масив вершин для кожної породженої трапеції. При другому проході виконується цикл repeat.
