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

[alan]

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

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

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

[alan]

Для примера очевидное и далекое от оптимальности решение:


I)
1. Организация. Точки в произвольном порядке записываем в масив.
2. Поиск. Перебираем весь масив от первого элемента до последнего. И для каждого элемента считаем расстояние до точки B, по формуле sqrt((b_x-x_i)^2+(b_y-y_i)^2). Из растояний выбираем минимальное(б) N минимальных, в) меньшие, чем R). Находим точку, которой соотвествует это расстояние.

Сколько платишь?

А как платить? За что? За решение + доказательство оптимальности? Не думаю что такое существует.
Поэтому и передумал в соответствующем разделе писать.
Хотя хорошо было бы иметь раздел в котором каждый мог бы делиться, "тем, что его беспокоит"