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