"Уточняющее прицеливание"

From

Andrew Plyako (2:5030/922.20)

To

Nickita A Startcev

Date

2002-05-07T15:58:54Z

Area

RU.ALGORITHMS

Hello Nickita.
05 May 02 14:51, you wrote to me:

 NS>>> Есть одномерный массив элементов (x,y,data), где x,y -
 NS>>> координаты этого псевдоточечного объекта. Диапазон в котором
 NS>>> лежат координаты известен.

 NS>>> Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n) ?
 AP>> Только если тем или иным способом упорядочить массив.

Ну, например, так:

Раз диапозон координат задан, то для простоты будем считать, что все координаты лежат в первом квадранте (x>0, y>0). Тогда, упорядочим точки по возрастанию расстояния до начала коориднат.
   Пусть нам надо найти точку ближайшую к точке A:
|  A
|          B
|___________
O

Заметим, что (по неравенству треугольника) |AB| > |OB| - |OA|.
Таким образом, если текущей "наиближайшей" точкой является точка С,
то мы можем не рассматривать все X: |OX| > |AC| + |OA|. То есть, обнаружив очередной претендент на звание "ближайшей точки", мы сразу отсекаем "хвост" нашего массива -- можем его не рассматривать.

Чем ближе исходная точка A к точке O, тем лучше. Как следствие, иногда может иметь смысл хранить сразу несколько "упорядочеваний" массива (относительно расстояния до разных точек).

Andrew

---
 * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)