3.4. ЗАДАЧІ РЕГІОНАЛЬНОГО ПОШУКУ
3.4.1. Загальні зауваження.
Запит у цій моделі визначає область (регіон) у d - вимірному просторі,
а результатом пошуку є звіт про множину точок файлу, яка міститься у цій
області (запит у режимі звіту). Іншою метою пошуку є підрахунок
числа точок в області запиту (запит у режимі підрахунку).
Припустимо, що файл - фіксований набір S із N записів.
Відповіддю на запит буде S' 
S. Відповіддю на запит у режимі підрахунку завжди буде єдине ціле
число k (k - потужність S'),
в той час як відповіддю на запит в режимі звіту будуть імена усіх k елементів S'.
Можна виділити два типи дій при обробці запиту:
- Пошук, тобто дії, які приводять до елементів шуканої
підмножини (зазвичай, послідовність порівнянь).
- Вибірка, тобто дії по складанню відповіді на запит ( для запитів у режимі звіту - це фактичне визначення шуканої підмножини).
- при аналізі запитів у режимі підрахунку всю обчислювальну роботу вбирає у себе "пошук"; при цьому очікується, що час запиту для гіршого випадку буде функцією f(N,d), яка залежить від розміру файла та розмірності;
- при аналізі у режимі звіту обчислювальна робота є комбінацією пошуку і вибірки, і та її частина, яка пов'язана з вибіркою, обмежена знизу числом k - потужністю S'.
У загальному випадку верхня оцінка часу запиту у режимі звіту така - O(f(N,d)+k×g(N,d)); f(N,d) - "час пошуку" і k×g(N,d) - "час вибірки".
W(k) - тривіальна нижня оцінка часу вибірки; W (log2Q(S)) - нижня оцінка кількості порівнянь для пошуку (використовується модель двійкового дерева розв'язків, яка підраховує число порівнянь, необхідних для доступу до елементів множини S' S всередині регіону запиту), де Q(S) - число різних підмножин S, отриманих як відповіді на запити.
Розглянемо: S - множина усіх точок, які мають одну і лише одну ненульову цілочисельну координату в інтервалі [-a,a]; N=2ad (мал. 3.19). 
і 
. Цей вибір можна здійснити a2d = (N/(2d))2d способами; 
нижня оцінка числа двійкових розв'язків рівна W(log (N/(2d))2d)= (dlog (N)). W(Nd) - тривіальна нижня оцінка пам'яті, яка зайнята під структуру даних пошуку. Для усіх алгоритмів, які описуються, час пошуку виражається у формі O(f(N,d)+k).
Мал. 3.19. Приклад множини S при d=2.
Одновимірний регіональний пошук.
Множина із N точок на осі x є файлом, а запитним регіоном є відрізок [x',x"] ( який називається x - регіоном). Ефективний регіональний пошук реалізується через метод, який базується на методі двійкового пошуку. Структура даних, яка забезпечує вказану дію, є прошитим двійковим деревом, тобто таким збалансованим двійковим деревом, листки якого додатково зв'язані у списку, який виражає порядок абсцис; дерево і список обробляються на фазах пошуку і вибірки. Оцінки: оптимальна як за часом запиту Q(logN+k), так і за пам'яттю Q(N).
