|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 09 Jul 2003 16:06:28
To : Dmitriy Iassenev
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
Hi!
> поиск ближайшего соседа выполняется за O(logN) с использованием памяти
> объёмом О(N). В то же время, перемещение/удаление/добавление точки,
похоже,
> будет пропорционально O(N*logN).
А каким методом делается поиск ближайшего соседа за O(logN)? И N тут именно
количество точек, а не ребер? Можно как-нибудь на пальцах объяснить или
ссылку, а то я не могу сообразить. Если допустим двигаться начиная с
произвольного ребра, поворачивая все время по ветке, более близкой к искомой
точке, до тех пор пока не зациклимся, то там по-моему больше чем O(logN), а
больше ничего придумать не могу.
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
