|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Saveliev 2:5020/400 23 Jul 2003 07:58:24
To : Dmitriy Goldobin
Subject : Re: Поиск ближайшей точки (сабж слетел)
--------------------------------------------------------------------------------
Dmitriy Goldobin wrote:
>
> ты немного не так понял - в ячейке регулярной сетки хранятся не ссылки на
> точки, входящие в эту ячейку, а ссылки на точки, до которых из этой ячейки
> могут быть ближайшее расстояния. Cсылка на одну и ту же точку может быть из
> разных ячеек. То есть как бы на диаграмму воронова наложили сетку и вписали
> в ее ячейки на какие ячейки диаграммы каждая из них накладывается.
OK, хотя я не уверен, что пересечение диаграммы Воронова со всеми
ячейками займет мало времени, возможно это тоже близко к O(N*N) - просто
мы вынесем сложность в предобработку. К тому же, если список точек
динамически меняется, в сортированный массив или дерево мы их
вставим/удалим без труда, а в такую структуру - нет.
> как осуществлять поиск ближайшей за logN по диаграмме воронова или по
> kd-tree я честно говоря так и не понял. надо попробовать реализовать, тогда
> пойму :)
Можно, кстати, про kd-tree почитать Препарату и Шеймоса - книжка хоть и
старая, но вполне на уровне, и из изданных на русском я других таких не
знаю ...
А что касается вопроса - так чего там искать, если список всех
потенциальных соседей (пересекаемых данной клеткой ячеек диаграммы
Воронова) уже есть? Кстати, в триангуляционных алгоритмах есть методы
локализации треугольников для данной точки, работающие в среднем за
O(n*log N), поэтому вместо диаграммы Воронова можно использовать
триангуляцию - ссылок, правда, не помню.
Анатолий
--- ifmail v.2.15dev5
* Origin: MELT InterNetNews site (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
