|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Serge Pashkov 2:5020/175.2 10 Jul 2003 09:54:06
To : Dmitriy Goldobin
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
Wed Jul 09 2003 17:12, Dmitriy Goldobin wrote to Serge Pashkov:
>> Есть то, что называется 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). Правда
DG> Segment
>> Tree/Range Tree там статические). Еще реализацию Kd-tree я встречал в
>> библиотеке Concorde.
DG> А как применить региональный поиск для поиска ближайшей точки? По-моему
DG> за logN при региональном поиске в итоге найдем не ближайшую точку, а
DG> точку, находящуюся в одном сегменте с искомой. Hо она же не обязательно
DG> ближайшая... Или может получится найти за logN минимального размера
DG> квадрат
DG> с центром в искомой точке и включающий по крайней мере одну точку
DG> множества,
DG> а потом уже среди точек входящих в квадрат перебором.
Да я согласен, что для Range Tree более естественны запросы типа "какие точки
заданного набора лежат в произвольном прямоугольнике" (window query).
Вот Kd-tree точьно использовался в Concorde для поиска 1 или нескольких
ближайших соседей (там эвристики TSP такие). Еще могу вспомнить, что Мартин
Хелд в своих программах VRONI (построение диаграммы Вороного для набора точке
и прямых) и FIST (быстрая триангуляция) для поиска ближайшего соседа
использовал двумерную решетку, число строк и столбцов в которой
пропорционально sqrt(N). По его утверждению, этот метод не хуже Kd tree на
практике.
Serge
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
