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