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

Лучше все-таки вначале кластеризовать точки и запомнить связи между соседними кластерами. Хотя бы точек по 10 в кластер — уже быстрей будет.

• находим перебором кластер, содержащий искомую точку
• рекурсивно сканируем связи, перебирая все точки в каждом кластере, формируем массив точек
• сортируем массив по r от заданной точки

Кластеризовать точки или области?

Ты предлагаешь кластеризовать точки при каждом запросе? Или по какому критерию ты предлагаешь проводить кластеризацию?

Точки кластеризовать. Один раз: в самом начале. Кластеризацию проще всего было бы сделать по равномерной сетке (прямоугольной). Но вроде бы уже должно быть полным-полно готовых алгоритмов для этой задачи. Правда, я что-то не нашел ничего.

Вот, кстати, дельная статейка по поводу k-means

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

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