|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Plyako 2:5030/922.20 07 May 2002 15:58:54
To : Nickita A Startcev
Subject : "Уточняющее прицеливание"
--------------------------------------------------------------------------------
NS>>> Есть одномерный массив элементов (x,y,data), где x,y -
NS>>> координаты этого псевдоточечного объекта. Диапазон в котором
NS>>> лежат координаты известен.
NS>>> Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n) ?
AP>> Только если тем или иным способом упорядочить массив.
Hу, например, так:
Раз диапозон координат задан, то для простоты будем считать, что все координаты
лежат в первом квадранте (x>0, y>0). Тогда, упорядочим точки по возрастанию
расстояния до начала коориднат.
Пусть нам надо найти точку ближайшую к точке A:
| A
| B
|___________
O
Заметим, что (по неравенству треугольника) |AB| > |OB| - |OA|.
Таким образом, если текущей "наиближайшей" точкой является точка С,
то мы можем не рассматривать все X: |OX| > |AC| + |OA|. То есть, обнаружив
очередной претендент на звание "ближайшей точки", мы сразу отсекаем "хвост"
нашего массива -- можем его не рассматривать.
Чем ближе исходная точка A к точке O, тем лучше. Как следствие, иногда может
иметь смысл хранить сразу несколько "упорядочеваний" массива (относительно
расстояния до разных точек).
Andrew
---
* Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
