А посоветуйте алгоритм/структуру данных для быстрейшего поиска точки (точек) в порядке удалённости от заданной в 2D?

И что тебе даст такая кластеризация? Порядок в рамках одного кластера будет менятся в зависимости от заданной точки. И более того при перечислении точек в порядке удаления от заданной мы будем прыгать из кластера в кластер и обратно.

Например. Даны точки на прямой с координатами -2, 0, 3, 5. Разбиваем их на два кластера {-2, 0} и {3, 5}. Для точки с координатой 2 порядок будет такой: (3, 0, 5, -2).

А посоветуйте алгоритм/структуру данных для быстрейшего поиска точки (точек) в порядке удалённости от заданной в 2D?

Встаю в любую координату 2D-плоскости и получаю список точек в порядке удалённости от текущей. BST-tree?

А закинуть все точки с координатами в базу данных и выбрать select'ом первые N,
отсортированные по (power(X-X0,2)+power(Y-Y0,2)), не спортивно, да?

Встаю в любую координату 2D-плоскости и получаю список точек в порядке удалённости от текущей. BST-tree?

Я правильно понимаю, есть, скажем, миллион точек разбросанных по плоскости, на вход программе даются координаты «старта», и на выходе она должна выдать ВСЕ миллион точек, отсортированные в порядке убывания от заданных координат, так?

Тогда самый простой и практически самый эффективный алгоритм — в момент получения координат «старта» тупо отсортировать точки по расстоянию и вывести. Получится O(NlogN).

Если выводить надо не все точки, а только в определённом радиусе, то строится R-дерево, по нему в прямоугольнике находятся нужные точки, и для них делается сортировка и вывод.

Если же задача прикладная, то можно тупо загнать эти точки, в какой-нибудь myisam, создать Spatial-индекс, и запрашивать их как-то так:

SELECT AsText(p), (POW(x(p)-123,2) + POW(y(p)-456,2)) AS sqrdist
FROM points
WHERE MBRContains(GeomFromText('POLYGON((100 400,100 500,200 500,200 400,100 400))'), p)
ORDER BY sqrdist

В Postgres нашёл PostGIS-«подсистему».

Сортировка без индекса? Или какой индекс ты здесь собираешься использовать? Особенно если учесть, что для разных запросов в общем случае придется использовать сортировку по разным выражениям.

Кроме того, нечто подобное уже предлагали, правда без использования БД. Но есть ли здесь польза от «универсальной» БД?

И как? Есть решение поставленной задачи эффективнее, чем просто сортировать по расстоянию от заданной?

Что значит «просто»? Чтобы сортировать по расстоянию от заданной, надо это расстояние ещё как-то вычислить.

Короче на 100К точках получился поиск ближайших 30 соседей за 0.001 сек.

поиск ближайших 30 соседей

Порядок следования соседей правильный?

Имелся в виду вопрос: даст ли GIS для этой задачи какое-нибудь преимущество?

Смотря перед чем. Можно накуриться и на C++ такое накодить, что любой PostGIS сдуется, но у меня не из чего выбирать, только PostGIS в общем-то - проще всего его использовать, т.к. postgresql нужной версии в проекте уже есть и выборка ближайших точек из 100К точек проходит за приемлимые 0.001 сек )

kiverattes

Можно накуриться и на C++ такое накодить, что любой PostGIS сдуется...

Cypher

Разбиение квадратной части плоскости в «квадродерево» сходно с разбиением кубической части пространства в разреженное воксельное октодерево - Sparse Voxel Octree (сокращенно S.V.O.), которое применяется в компьютерной графике.

"В итоге, перейдя от PostGIS к узкоспециализированному решению на C++, мы получили ускорение с 2к до 380к (в 190 раз)."