Re: Сортировка комплексных чисел?

From

Nick Kovaliov ()

To

Pertzel Family

Date

2002-08-09T11:50:17Z

Area

RU.ALGORITHMS

From: "Nick Kovaliov" <Nick@urm.ru>

    > Тогда я бы сделал кластеризацию:
    > поделил бы квадрат, в который они
    > попали, на 4 маленьких, каждый из
    > них, еще на 4, и т.д.
[... Skipped ...]
Это называется q-tree ...
Есть ещё так называемые
Vantage Point Tree - VP tree -
Там "кластеризация", как ты её называешь,
делается не квадратами, а окружностями.
Причём, работает в
ЛЮБОМ метрическом пространстве.
Есть PDF, где достал его, уже и не помню ...

А можно сделать ещё не так -
разбить пространство на кластеры.
В твоём случае, например, на квадратики.
Идея хеширования -
Для данного квадратика создаёшь список
тех точек, которые могут оказаться ближайшими.
Как быстро создать эту структуру
для кластеров любой формы, я не знаю.
Но вычислять по ней можно ОЧЕНЬ быстро.

До встречи, всего наилучшего !

--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)