Ближайшая точка, типа прикладная Опции Рейтинг

[alan]

Представьте, что у вас есть множество А из M точек на плоскости (x_i,y_i). Есть информация о них - по две координаты.

Потом нам дают еще одну точку - B(b_x,b_y). Нужно найти:
а) Точку из множества А ближайшую к B.
б) N ближайших точек к B.
в) Все точки на растоянии меньше чем R от B

Задача - оптимально организовать информацию о точках А. Оптимальность определяется средней скоростью выполнения а), б) или в).

[alan]

Ну давай забудем лучше о памяти, а то если все помнить и учитывать останемся с носом.

Итак главное скорость.
Я так понял, что для поиска ближайшей точки ты предлагаешь проследовать от верха дерева к низу? Итого порядка log(N) операций?

Если разбить на одинаковые квадратики, то мы сможем сразу получить номер квадрата имея координаты точки В. Если везет то ближайшая точка получается за 1 операцию.
Мне вот только не ясно, что будет если не везет...

[NLIzer]

Я так понял, что для поиска ближайшей точки ты предлагаешь проследовать от верха дерева к низу? Итого порядка log(N) операций?

Думаю, что поиск ближайшей точки будет происходить следующим образом:
Для точки B проходом по дереву сверху-вниз определяется минимальный квадрант имеющий точки (точка В принадлежит этому квадранту). В этом квадранте последовательно определяется подквадрант имеющий точки и ближайший к точке В. В этом подквадранте определяется ближайшая точка к B и определяется ее расстояние до точки B – расстояние R. Далее ищем все точки на расстоянии меньше чем R от B (поиск в)) с учетом уже просмотренных квадрантов. Если точка на меньшем расстоянии найдена, то опять вычисляем R и повторяем поиск.