26. Региональный поиск. Алгоритм с предобработкой. Оценки.

Задачи регионального поиска

Есть множество объектов и некоторая область.

1) Сколько объектов принадлежат области?

Предположим, есть n точек на плоскости. Область – прямоугольник со сторонами параллельными осям координат (условие параллельности необходимо, если область составлена из нескольких прямоугольников).

В общем случае данная задача решается за O(n).

Ном можно ускорить О(logn).

Выберем точку Р, тогда числом векторного доминирования I(P) называется количество точек, которые лежат левее и ниже точки Р.

Количество точек внутри прямоугольника вычисляется по формуле

К = I(P2)-I(P3)-I(P1)+I(P0)

Найдем область, где I(P) постоянно. Через каждую точку проводим вертикальную и горизонтальную прямые(время решения O(n^2)). Внутри одной ячейки I(P) постоянно. То есть для решения основной задачи необходимо заранее вычислить I(P) каждой ячейки и определенным образом их упорядочить.

Затем определяется принадлежность вершин прямоугольника(области) ячейкам методом бинарного поиска(деления пополам) за время О(logn). Находим по формуле число К.

Таким образом на предобработку требуется O(n^3), на обработку одного запроса О(logn). Если множество точек не меняется, а запросов много, то применяем этот метод.

Недостаток метода-объем памяти для хранения данных O(n^2).