|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Pashkov 2:5020/175.2 09 Jul 2003 16:08:20
To : Dmitriy Goldobin
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
Wed Jul 09 2003 14:41, Dmitriy Goldobin wrote to Dmitriy Iassenev:
DG> From: "Dmitriy Goldobin" <gold@ems.ru>
DG> Hi!
>> > Можно ли (и как) так хранить множество точек на плоскости, чтобы поиск
>> > точки, ближайшей к заданной, занимал O(logN)? Hу и чтобы
>> > перемещение/удаление/добавление точки не было при этом чересчур
>> > дорогостоящей операцией, а тоже что-нибудь <= O(N).
>>
>> Стройте диаграмму Вороного.
DG> Сложность построения O(N*logN), да и главное - что потом с этой
DG> диаграммной делать, не попадание же в многоугольники перебором проверять?
DG> :) Видимо еще потом делать что-то вроде дерева, деля плоскость прямыми
DG> вдоль ребер диаграммы, но отсекаться на каждом шаге будет меньше половины
DG> точек, в
DG> худшем случае каждый раз всего одна. Так что поиск получается от O(logN)
DG> до O(N) в зависимости от расположения точек.
DG> Может побыстрее что-то есть? Вот допустим в одномерном пространстве
DG> достаточно отсортировать по координате и бинарным поиском. :) Может и
DG> двумерном можно как-то хитро сортировать?
Есть то, что называется Range Tree/Segment Tree (в временем предобработки
O(N(logN)**(d-1)) и средним временем поиска типа (log N)**d + k для
d-мерного пространства) или Kd-tree (с временем предобработки типа
O(NlogN) и средним временем поиска O(n**(1-1/d) + k), где k - размер
результирующего запроса)
Примеры реализации обоих есть, например, в CGAL (www.cgal.org). Правда Segment
Tree/Range Tree там статические). Еще реализацию Kd-tree я встречал в
библиотеке Concorde.
Serge
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
