|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 09 Aug 2002 11:50:17
To : Pertzel Family
Subject : Re: Сортировка комплексных чисел?
--------------------------------------------------------------------------------
> Тогда я бы сделал кластеризацию:
> поделил бы квадрат, в который они
> попали, на 4 маленьких, каждый из
> них, еще на 4, и т.д.
[... Skipped ...]
Это называется q-tree ...
Есть ещё так называемые
Vantage Point Tree - VP tree -
Там "кластеризация", как ты её называешь,
делается не квадратами, а окружностями.
Причём, работает в
ЛЮБОМ метрическом пространстве.
Есть PDF, где достал его, уже и не помню ...
А можно сделать ещё не так -
разбить пространство на кластеры.
В твоём случае, например, на квадратики.
Идея хеширования -
Для данного квадратика создаёшь список
тех точек, которые могут оказаться ближайшими.
Как быстро создать эту структуру
для кластеров любой формы, я не знаю.
Hо вычислять по ней можно ОЧЕHЬ быстро.
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
