Геометричний пошук, Детальна інформація

Означення. Якщо ребро графа G перетинає обидві горизонтальні сторони трапеції, то воно називається накриваючим.

Після визначення медіани ymed трапеції R множина ребер графа G, яка перетинає R, проглядається зліва направо та розділяється на дві множини, що відносяться до R1 та R2. Якщо зустрічається накриваюче ребро, то воно стає правою боковою границею нової трапеції, яка обробляється незалежно.

Розбиття трапеції

Кожній трапеції R відповідає дерево двійкового пошуку T(R), пожен вузол якого пов’язано з лінійною перевіркою. Вузли можуть бути двох типів: \xF0D1\xF020- вузли, якщо перевірка відбувається відносно горизонталі, та О - вузли, якщо перевірка відбувається відносно прямої, яка містить ребро графа. Корінь завжди є \xF0D1\xF020- вузлом. Оскільки дві крайні вершини графа не беруть участі у розбитті трапеції, то кількість \xF0D1 - вузлів у дереві пошуку дорівнює N - 2.

Дерево пошуку, яке відповідає трапеції

d

c

b

a

y(p)d

P2

P1

P4

P3

x(p)

5

4

3

2

1

2

2

1

1

3

1

1

1

1

1