|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Goldobin 2:5020/400 09 Jul 2003 17:12:43
To : Serge Pashkov
Subject : Re: Перетаскивание ребер и вершин. Может попроще сначала задачку?
--------------------------------------------------------------------------------
Hi!
> Есть то, что называется 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.
А как применить региональный поиск для поиска ближайшей точки? По-моему за
logN при региональном поиске в итоге найдем не ближайшую точку, а точку,
находящуюся в одном сегменте с искомой. Hо она же не обязательно
ближайшая... Или может получится найти за logN минимального размера квадрат
с центром в искомой точке и включающий по крайней мере одну точку множества,
а потом уже среди точек входящих в квадрат перебором.
Bye.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
