|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Nozhenko 2:5020/175.1 10 Jul 2003 03:47:22
To : Dmitriy Goldobin
Subject : Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
>> > точки, ближайшей к заданной, занимал 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), и использовать обычные сортировку/бинарный поиск.
Serge
--- Golded 2.41+
* Origin: Moccoletto (2:5020/175.1)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
