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

From

Michael Ryazanov (2:5030/1006.64)

To

Nickita A Startcev

Date

2002-05-05T15:09Z

Area

RU.ALGORITHMS

▐┤E╚°' Nickita!

01.05 22:36 Nickita A Startcev, 2:5030/1039.8 -> All

 NAS> Есть одномерный массив элементов (x,y,data), где x,y - координаты этого
 NAS> псевдоточечного объекта. Диапазон в котором лежат координаты известен.
 NAS> Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n) ?

   Память дополнительную можно использовать?

 NAS> Есть ли решение более быстрое чем нижеприведенное?
 NAS> 1) берем расстояние до первого объекта, запоминаем вместе с номером
 NAS> объекта.
 NAS> 2) перебираем подряд оставшиеся объекты, если попался более близкий -
 NAS> 'перезапоминаем' расстояние и номер.

   Если без дополнительной памяти, можно предложить некую оптимизацию (если объектов достаточно много и расположены они более-менее равномерно). Надо отсотрировать массив в лексикографическом порядке (x, y). Далее, двоичным (и т.п.) поиском находим элемент с x, ближайшим к X0, и бежим по массиву в обе стороны, ищя минимум расстояния. Когда |x[i] - X0| станет больше найденного минимального расстояния, дальше можно не искать.
   Если можно использовать дополнительную память, то тут раздолье. :-) Сетку построить, деревья всякие-разные...

                                                                      |V|uxau/\
--- -- - ·
 * Origin:             Ф И З Ф А К - Ч Е М П И О H !           (2:5030/1006.64)