Удалить ближайших

[vregess]

Я могу ошибаться, но возможно подойдут вот эти ребята:
1) Spatial database
2) K-D-tree
3) M-tree
4) Quadtree
5) R-tree

мб M-tree самый правильный. Вот тут java applet с примером есть: http://www.cmarschner.net/mtree.html
Я совершенно не разбираюсь в этих алгоритмах, просто однажды просили поискать.

[Igors]

Я могу ошибаться, но возможно подойдут вот эти ребята:

Ребята сильные, но ни один из них не выглядит ни простым ни дешевым для реализации. Плюс смущает одно обстоятельство - нужно ведь просто проредить/отфильтровать (а совсем не весь функционал), хочется обойтись без полномасштабного построения дерева.

В любом случае спасибо за подборочку

[vregess]

Ребята сильные, но ни один из них не выглядит ни простым ни дешевым для реализации. Плюс смущает одно обстоятельство - нужно ведь просто проредить/отфильтровать (а совсем не весь функционал), хочется обойтись без полномасштабного построения дерева.

Если просто - то перебор, если быстро, то не просто)
Но я понимаю. Эти алгоритмы не такие простые, для "простой" задачи. Я и сам бы не рвался их использовать, мб как вариант для будущих улучшений.

[Akon]

Наложить на плоскость регулярную решетку, точки, покрытые решеткой удалить, в неплотностях решетки может оказаться >1 точки, поэтому вторым проходом оставляем только одну любую точку в каждой неплотности.

Берем круг, к нему приставляем еще круг и т.д. по плоскости. Получается решетка, между кругами есть промежутки (неплотности). Коордтнаты центров кругов известны. Алгоритм исключения точек простейший.

[Igors]

Берем круг, к нему приставляем еще круг и т.д. по плоскости. Получается решетка, между кругами есть промежутки (неплотности). Коордтнаты центров кругов известны. Алгоритм исключения точек простейший.

Так что, если "взяли круг" - так уже мы знаем какие точки в него попадут? Или можем это быстро определить? Не вижу каким образом.

Также: если я правильно понял, центры кругов образуют регулярную решетку, и полагается что в 1 круге - не более 1 точки. Тогда 2 близкие точки могут быть в соседних кругах, и одна из них не будет удалена вторым проходом по "неплотностям"

[Disa]

Мб попробовать решение по аналогии с closest pair algorithm?

То есть
1) Делить множество пополам относительно некого pivot (по x-вой координате). Pivot - это то, что в русскоязычной литературе называется компаранд (по ссылке - средняя точка).
2) Рекурсивно вызывать функцию для каждой из двух половинок, где "внизу" дерева рекурсии проверяем расстояние между ними, если оно меньше - удаляем точки (тут h - величина фиксированная нами).
3) Аналогично поменять функцию объединения(split function, по ссылке это стадия объединения), то есть множество C(pi) так же для фиксированного h.

Время работы - это сумма времени работы рекурсивных вызовов + функция объединения.

http://e-maxx.ru/algo/nearest_points

[Igors]

Мб попробовать решение по аналогии с closest pair algorithm?

То есть

Так я пробовал   На сильном прореживании (когда расстояние D мало) - все очень прилично, но при бОльших D опять сваливаемся в перебор. В closest pair этой проблемы нет - ищем минимальное, ну D и уменьшается автоматычно