|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Iassenev 2:5020/400 09 Jul 2003 19:28:00
To : Dmitriy Goldobin
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
> > поиск ближайшего соседа выполняется за O(logN) с использованием памяти
> > объёмом О(N). В то же время, перемещение/удаление/добавление точки,
> похоже,
> > будет пропорционально O(N*logN).
>
> А каким методом делается поиск ближайшего соседа за O(logN)? И N тут
именно
> количество точек, а не ребер? Можно как-нибудь на пальцах объяснить или
> ссылку, а то я не могу сообразить. Если допустим двигаться начиная с
> произвольного ребра, поворачивая все время по ветке, более близкой к
искомой
> точке, до тех пор пока не зациклимся, то там по-моему больше чем O(logN),
а
> больше ничего придумать не могу.
Сам по себе метод весьма нетривиален. Могу дать ссылку на книгу
"Вычислительная геометрия", авторы Препарата и Шеймос ("Геометрический поиск
: Задача локализации точки, метод детализации триангуляции Киркпатрика"),
впрочем реализаций диаграммы Вороного для любых размерностей полно в
интернете (в том числе и с запросами на локализацию точки). В этом методе
используется граф, двойственный диаграмме Вороного (триангуляция Делоне).
С уважением,
Дмитрий Ясенев.
P.S. Есть ещё метод планарного сепаратора, но я не разбирался как он
работает.
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
