Геом Поиск Локализация

Сентябрь 3, 2022

Главная
Алгебра
Геом Поиск Локализация

Содержание

2. 30.03.2007 Геометрический поиск Локализация точки Геометрический поиск Абстрактная модель поиска: некоторый набор данных – «файл»; некоторый
3. 30.03.2007 Геометрический поиск Локализация точки Геометрический поиск 4 меры оценки ресурсов при анализе геометрических алгоритмов поиска:
4. 30.03.2007 Геометрический поиск Локализация точки Фазы обработки при геометрическом поиске Предобработка Обработка запроса Корректировка СД
5. 30.03.2007 Геометрический поиск Локализация точки Пример: бинарный поиск в массиве из n элементов Время предобработки: сортировка
6. 30.03.2007 Геометрический поиск Локализация точки Региональный поиск (подсчет). Региональный поиск: даны n точек на плоскости. Сколько
7. 30.03.2007 Геометрический поиск Локализация точки Региональный поиск. Метод локусов Прямоугольник = 4 вершины. Можно заменить запрос
8. 30.03.2007 Геометрический поиск Локализация точки Связь между доминированием и региональным поиском Число точек N(p1p2p3p4) в прямоугольнике
9. 30.03.2007 Геометрический поиск Локализация точки Из точек p опущены перпендикуляры на оси x и y, а
10. 30.03.2007 Геометрический поиск Локализация точки Предобработка: сортировка O(n log n) + решетка O(n3) O(n2) Запрос: 2
11. 30.03.2007 Геометрический поиск Локализация точки Задача локализации точки Файл = разбиение геометрического пространства на области, Образец
12. 30.03.2007 Геометрический поиск Локализация точки n – число вершин простого многоугольника Принадлежность точки z внутренности простого
13. 30.03.2007 Геометрический поиск Локализация точки k := o; for i := 1 to n do {цикл
14. 30.03.2007 Геометрический поиск Локализация точки Выпуклый многоугольник Локализации точки в простом многоугольнике p2 p1 q z*
15. 30.03.2007 Геометрический поиск Локализация точки Локализации точки в простом многоугольнике Звездный многоугольник Ядро – множество не
16. 30.03.2007 Геометрический поиск Локализация точки Звездный многоугольник Локализации точки в простом многоугольнике Запрос: O(log n) Память:
18. Скачать презентацию

Слайд 2

30.03.2007
Геометрический поиск Локализация точки
Геометрический поиск
Абстрактная модель поиска:
некоторый набор данных – «файл»;
некоторый

новый элемент данных – «образец».
Поиск – установление связи между образцом и файлом.
Геометрический поиск
Файлы – сложные геометрические структуры: множества точек, многоугольники, графы и т.п.
Образцы: точки, регионы и т.п.
Запрос на поиск (на обработку – просмотр файла)
Пример: поиск в массиве чисел.
Уникальный запрос. Массовый запрос.
Предобработка – структуризация данных (сортировка)

Слайд 3

30.03.2007
Геометрический поиск Локализация точки
Геометрический поиск
4 меры оценки ресурсов
при анализе геометрических

алгоритмов поиска:
Время предобработки. Сколько времени необходимо для организации данных перед поиском?
Время запроса. Сколько времени необходимо для ответа на один запрос?
Память. Сколько памяти необходимо для структуры данных (СД)?
Время корректировки. Предъявлен элемент данных. Сколько времени потребуется на его включение в СД или исключение из неё?

Слайд 4

30.03.2007
Геометрический поиск Локализация точки
Фазы обработки при геометрическом поиске
Предобработка
Обработка запроса
Корректировка

СД

Слайд 5

30.03.2007
Геометрический поиск Локализация точки
Пример: бинарный поиск в массиве из n элементов
Время

предобработки: сортировка – O (n log n)
Время запроса: ⎡log2 (n + 1)⎤ или O (log n)
Память: O (n)
Время корректировки: O (n)

Слайд 6

30.03.2007
Геометрический поиск Локализация точки
Региональный поиск (подсчет).
Региональный поиск: даны n точек

на плоскости.
Сколько из них лежит внутри заданного прямоугольника, стороны которого параллельны координатным осям?
Т.е. сколько точек p = (x, y) удовлетворяют неравенствам
a ≤ x ≤ b, c ≤ y ≤ d для заданных a, b, c и d ?

В форме отчет – перечислить внутренние точки. Уникальный региональный запрос – O(n) (оптимально). Метод локусов. Локус – геометрическое место точек, в пределах которого ответ не меняется.

Слайд 7

30.03.2007
Геометрический поиск Локализация точки
Региональный поиск. Метод локусов
Прямоугольник = 4 вершины.
Можно заменить

запрос с прямоугольником четырьмя подзадачами, по одной на каждую из его вершин.
Подзадача, связанная с вершиной p: определить число точек Q(p) исходного множества, которые удовлетворяют неравенствам x ≤ x(p) и y ≤ y(p), т.е. числа точек в левом нижнем квадранте, определяемом вершиной p.

векторное доминирование
Говорят, что точка (вектор) v доминирует над w, тогда и только тогда, когда для всех индексов (координат) i верно условие vi ≥ wi. На плоскости точка v доминирует над w тогда и только тогда, когда w лежит в левом нижнем квадранте, определяемом v.

Сколько точек “юго-западнее” p?

Слайд 8

30.03.2007
Геометрический поиск Локализация точки
Связь между доминированием и региональным поиском
Число точек

N(p1p2p3p4) в прямоугольнике p1p2p3p4 определяется следующим образом:
N(p1p2p3p4) = Q(p1) - Q(p2) - Q(p4) + Q(p3)

Региональный поиск. Метод локусов

На плоскости существуют области удобной формы, внутри которых число доминирования Q является константой. Локусы.
См. папку «1Метод локусов»

Слайд 9

30.03.2007
Геометрический поиск Локализация точки
Из точек p опущены перпендикуляры на оси x

и y, а полученные линии продолжены в бесконечность. Они создают решетку из (n+1)2 прямоугольников.

Региональный поиск. Метод локусов

Слайд 10

30.03.2007
Геометрический поиск Локализация точки
Предобработка: сортировка O(n log n) + решетка O(n3)

O(n2)
Запрос: 2 бинарных поиска O(log2n)

Региональный поиск. Метод локусов

Слайд 11

30.03.2007
Геометрический поиск Локализация точки
Задача локализации точки
Файл = разбиение геометрического пространства на

области,
Образец для запроса = точка.
Локализация состоит в определении области, содержащей запрошенную точку.
Планарное подразбиение плоскости прямолинейными отрезками
Многоугольники

Слайд 12

30.03.2007
Геометрический поиск Локализация точки
n – число вершин простого многоугольника
Принадлежность точки z

внутренности простого многоугольника – O(n) без предобработки

Локализации точки в простом многоугольнике

Слайд 13

30.03.2007
Геометрический поиск Локализация точки
k := o;
for i := 1 to n

do {цикл по ребрам}
if not горизонтальное (ребро[i]) then
if ребро[i] пересекает L нижним концом справа от z
then k := k + 1;
if Odd(k) then z – внутри else z – снаружи;

Локализации точки в простом многоугольнике

Слайд 14

30.03.2007
Геометрический поиск Локализация точки
Выпуклый многоугольник
Локализации точки в простом многоугольнике
p2
p1
q
z*
z
p4
p3
p5
p7
p6
p8
p9
p10
Запрос: O(log n)
Память:

O(n)
Предобработка: O(n)

Слайд 15

30.03.2007
Геометрический поиск Локализация точки
Локализации точки в простом многоугольнике
Звездный многоугольник
Ядро – множество

не внешних для P точек, из которых «видны» все точки многоугольника (O(n)).
Ядро не пусто ↔ многоугольник звездный.

Слайд 16

30.03.2007
Геометрический поиск Локализация точки
Звездный многоугольник
Локализации точки в простом многоугольнике
Запрос: O(log n)
Память:

O(n)
Предобработка: O(n)

Геом Поиск Локализация

Содержание

30.03.2007Геометрический поиск Локализация точкиГеометрический поискАбстрактная модель поиска:некоторый набор данных – «файл»;некоторый

30.03.2007Геометрический поиск Локализация точкиГеометрический поиск4 меры оценки ресурсов при анализе геометрических

30.03.2007Геометрический поиск Локализация точкиФазы обработки при геометрическом поискеПредобработка Обработка запроса Корректировка

30.03.2007Геометрический поиск Локализация точкиПример: бинарный поиск в массиве из n элементовВремя

30.03.2007Геометрический поиск Локализация точкиРегиональный поиск (подсчет). Региональный поиск: даны n точек

30.03.2007Геометрический поиск Локализация точкиРегиональный поиск. Метод локусовПрямоугольник = 4 вершины.Можно заменить

30.03.2007Геометрический поиск Локализация точкиСвязь между доминированием и региональным поиском Число точек

30.03.2007Геометрический поиск Локализация точкиИз точек p опущены перпендикуляры на оси x

30.03.2007Геометрический поиск Локализация точкиПредобработка: сортировка O(n log n) + решетка O(n3)

30.03.2007Геометрический поиск Локализация точкиЗадача локализации точкиФайл = разбиение геометрического пространства на

30.03.2007Геометрический поиск Локализация точкиn – число вершин простого многоугольникаПринадлежность точки z

30.03.2007Геометрический поиск Локализация точкиk := o;for i := 1 to n

30.03.2007Геометрический поиск Локализация точкиВыпуклый многоугольникЛокализации точки в простом многоугольникеp2p1qz*zp4p3p5p7p6p8p9p10Запрос: O(log n)Память:

30.03.2007Геометрический поиск Локализация точкиЛокализации точки в простом многоугольникеЗвездный многоугольникЯдро – множество

30.03.2007Геометрический поиск Локализация точкиЗвездный многоугольникЛокализации точки в простом многоугольникеЗапрос: O(log n)Память:

Похожие презентации

30.03.2007
Геометрический поиск Локализация точки
Геометрический поиск
Абстрактная модель поиска:
некоторый набор данных – «файл»;
некоторый

30.03.2007
Геометрический поиск Локализация точки
Геометрический поиск
4 меры оценки ресурсов
при анализе геометрических

30.03.2007
Геометрический поиск Локализация точки
Фазы обработки при геометрическом поиске
Предобработка
Обработка запроса
Корректировка

30.03.2007
Геометрический поиск Локализация точки
Пример: бинарный поиск в массиве из n элементов
Время

30.03.2007
Геометрический поиск Локализация точки
Региональный поиск (подсчет).
Региональный поиск: даны n точек

30.03.2007
Геометрический поиск Локализация точки
Региональный поиск. Метод локусов
Прямоугольник = 4 вершины.
Можно заменить

30.03.2007
Геометрический поиск Локализация точки
Связь между доминированием и региональным поиском
Число точек

30.03.2007
Геометрический поиск Локализация точки
Из точек p опущены перпендикуляры на оси x

30.03.2007
Геометрический поиск Локализация точки
Предобработка: сортировка O(n log n) + решетка O(n3)

30.03.2007
Геометрический поиск Локализация точки
Задача локализации точки
Файл = разбиение геометрического пространства на

30.03.2007
Геометрический поиск Локализация точки
n – число вершин простого многоугольника
Принадлежность точки z

30.03.2007
Геометрический поиск Локализация точки
k := o;
for i := 1 to n

30.03.2007
Геометрический поиск Локализация точки
Выпуклый многоугольник
Локализации точки в простом многоугольнике
p2
p1
q
z*
z
p4
p3
p5
p7
p6
p8
p9
p10
Запрос: O(log n)
Память:

30.03.2007
Геометрический поиск Локализация точки
Локализации точки в простом многоугольнике
Звездный многоугольник
Ядро – множество

30.03.2007
Геометрический поиск Локализация точки
Звездный многоугольник
Локализации точки в простом многоугольнике
Запрос: O(log n)
Память: