Геометрический поиск Алгоритмы регионального поиска

Сентябрь 3, 2022

Главная
Алгебра
Геометрический поиск Алгоритмы регионального поиска

Содержание

2. 13.04.2007 Региональный поиск Региональный поиск Файл: множество точек S = {p1, p2, …, pn} Образец: регион
3. 13.04.2007 Региональный поиск Одномерный случай 1. Сортировка + бинарный поиск Региональный поиск 2. Равномерная сетка
4. 13.04.2007 Региональный поиск Метод сетки Сетка: m × m Построение: O (m2 + n) Коэффициент заполнения
6. Скачать презентацию

Слайд 2

13.04.2007
Региональный поиск
Региональный поиск
Файл: множество точек S = {p1, p2, …, pn}
Образец:

регион (область) R
Регион = прямоугольник
Тип задач:
Задача подсчета: k = ⎢S′ ⎢, где S′ ⊂ S
Задача отчета: S′
Два вида действий при обработки запроса:
Поиск (приводит к элементам S′ )
Выборка (извлечение отчета S′ )
O(f(n, d) + k)

Слайд 3

13.04.2007
Региональный поиск
Одномерный случай
1. Сортировка + бинарный поиск
Региональный поиск
2. Равномерная сетка

Слайд 4

13.04.2007
Региональный поиск
Метод сетки
Сетка: m × m
Построение: O (m2 + n)
Коэффициент заполнения

ячейки: M = n / m2
m = sqrt (n / M)
Пусть R → k = ⎢S′ ⎢
В среднем: «равномерно»
по k / M ячейкам
O ( k / M + k) = O ( k )
Худший случай O (m2 + n)