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

From

Evgenij Masherov (2:5020/175.2)

To

Nickita A Startcev

Date

2002-05-06T08:37:27Z

Area

RU.ALGORITHMS

Wed May 01 2002 22:36, Nickita A Startcev wrote to All:



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

 NAS> Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n) ?

 NAS> Есть ли решение более быстрое чем нижеприведенное?

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

0. Эта задача, практически в такой же постановке, описана у Кнута (т.3, п.
6.5)
1. Простейшее предлагаемое там решение - построить вспомогательный массив, в
котором ключом являются пары округленных значений (х,у), а по этому ключу
вызывается список точных значений (х,у), принадлежащих этому подклассу
(т.е. за О(1) находится от одной до четырех подкарт, а затем по каждой из них
делается линейгый поиск)
2. Более сложное предлагаемое там решение - бинарное дерево, причем узел его
соответствует паре (город, радиус), левая ссылка - города с расстоянием менее
радиуса, правая - более. (Уточнения к Кнуту...)

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)