|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Iassenev 2:5020/400 10 Jul 2003 12:25:43
To : Serge Nozhenko
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
> >> > точки, ближайшей к заданной, занимал O(logN)? Hу и чтобы
> >> > перемещение/удаление/добавление точки не было при этом чересчур
> >> > дорогостоящей операцией, а тоже что-нибудь <= O(N).
> >>
> >> Стройте диаграмму Вороного.
>
> DG> Сложность построения O(N*logN), да и главное - что потом с этой
> DG> диаграммной делать, не попадание же в многоугольники перебором
проверять?
> DG> :) Видимо еще потом делать что-то вроде дерева, деля плоскость
прямыми
> DG> вдоль ребер диаграммы, но отсекаться на каждом шаге будет меньше
половины
> DG> точек, в худшем случае каждый раз всего одна. Так что поиск
получается от
> DG> O(logN) до O(N) в зависимости от расположения точек.
>
> Жють.
>
> Ввести линейную упорядоченность типа less((x1, y1), (x2, y2)) = (x1 < x2
||
> x1 == x2 && y1 < y2), и использовать обычные сортировку/бинарный поиск.
точка, найденная предложенным методом, в большинстве случаев не будет
ближайшей.
С уважением,
Дмитрий Ясенев.
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
