3.4.3. МЕТОД ДЕРЕВА РЕГІОНІВ
У d=2 будь-який відрізок розбивається на більше ніж три стандартні відрізки. Мінімізація кількісті стандартних відрізків - головна ідея методу дерева регіонів.
Розглянемо множину на осі х, яка складається з N абсцис, які нормалізуються до нормальних чисел із інтервалу [1, N] по всій величині. N абсцис визначають N-1 елементарних відрізків [i, i + 1] для і = 1, 2, ... ,N - 1.
Будь-який відрізок, кінці якого належать множині із N заданих абсцис, може бути розбитий деревом відрізків T(1, N) на більше ніж 
стандартних відрізки. Кожен стандартний відрізок віднесений до одного з вузлів T(1, N), а ті вузли, які визначають розбиття відрізка [i, j], називаються вузлами віднесення.
Дерево відрізків T(1, N) використовується при пошуці по х-координаті. Цей пошук визначає універсальну множину вузлів (вузлів віднесення). Кожен такий вузол v відповідає множині із (E[v] - B[v]) абсцис, тобто, множині із (E[v] - B[v]) точок на площині. Ординати цих точок утворюють звичайне двійкове дерево для регіонального пошуку в у-напрямку. У результаті побудована нова структура даних називається деревом регіонів; його первинною структурою є дерево відрізків, заданих на абсцисах точок вихідної множини S. У кожному вузлі цього дерева є вказівник на прошите двійкове дерево пошуку (вторинні структури). При цьому розглядається два підходи щодо розбиття на стандартні інтервали та визначення вузлів віднесення. Перший підхід полягає у тому, що проекції на вісь ОХ заданої множини точок розбивають вісь абсцис на множину інтервалів. На основі чого будується дерево відрізків. Вузлами віднесення такого дерева є вузли, які представляють інтервали, що фрагментують проекцію на вісь абсцис заданого регіону, тобто вставимі інтевали (мал. 3.23). Другий підхід, запропонований у монографії [1], полягає у тому, що вузли віднесення являють собою три стандартних інтервали, на які розбивається заданий регіон (мал. 3.24.) Дерево регіонів будується рекурсивно:
- Початкове дерево відрізків Т* відповідає множині {x1(p): p
S}. Для кожного вузла v із Т* позначимо через Sd(v)- множину точок з S.
Визначимо (d - 1)-вимірну множину: Sd - 1(v) = {(x2(p), ... , xd(p)): p Sd(v)}.
- Вузол v із Т* має вказівник на дерево регіонів для Sd -1(v).
Мал. 3.23. Ілюстрація застосування дерева регіонів. Перший підхід. Початковий регіон розбитий множиною точок на чотири інтервали, які відповідають вузлам віднесення (а). Пошукові дії показані на мал. (б).
Мал. 3.24. Ілюстрація застосування дерева регіонів. Підхід Шеймоса. Початковий регіон розбитий трьома стандартними відрізками (а). Пошукові дії показані на мал. (б).
Теорема 3.16 Регіональний пошук на d-вимірному файлі із N точок можна провести (N logd-1 N, logd N) - алгоритмом, якщо затрати O(N logd-1 N) часу на попередню обробку. Цей алгоритм заснований на методі дерева регіонів, і, зокрема, для d=2 час запиту, пам'ять і час попередньої обробки такі: O(log2 N + k), O(N log N) i O(N log N) відповідно.
