как мне выбрать подмножество точек с обычной плотностью? Более формально,

Учитывая

1. набор Aнеравномерно расположенных точек,
2. метрику расстояния dist(например, евклидово расстояние),
3. и целевая плотность d,

как я могу выбрать наименьшее подмножество B, которое удовлетворяет ниже?

• для каждой точки xв A,
• существует точка yв B
• , которая удовлетворяет условию dist (x,y)

На данный момент лучше всего

• начать с Aсама
• выбрать ближайшую (или просто особенно близкую) пару точек
• случайным образом исключить один из них
• повторить до тех пор, пока выполняется условие

и повторить всю процедуру на удачу. Но есть ли лучшие способы?

Я пытаюсь сделать это с 280 000 точек 18-D, но мой вопрос касается общей стратегии. Поэтому я также хочу знать, как это сделать с 2-D точками.И мне действительно не нужна гарантия наименьшего подмножества. Любой полезный метод приветствуется. Спасибо.

восходящий метод

• выбрать случайную точку
• выбрать среди невыбранных y, для которых min(d(x,y) для x в выбранном)наибольшее
• Продолжай!

Я назову его восходящим, а то, что я изначально опубликовал, — сверху вниз. Вначале это намного быстрее, поэтому для разреженной выборки это должно быть лучше?

показатель производительности

Если гарантия оптимальности не требуется, я думаю, что эти два индикатора могли бы быть полезны:

• радиус покрытия: max {y in unselected} min(d(x,y) for x в выбранном)
• радиус экономии: min {y в выбранном != x} min(d(x,y) для x в выбранном)

RC минимально разрешен d, и между ними нет абсолютного неравенства. Но RC предпочтительнее.

Мои маленькие методы.

Для небольшой демонстрации этого «показателя производительности» я сгенерировал 256 двумерных точек, распределенных равномерно или по стандартному нормальному распределению. Затем я попробовал с ними методы «сверху вниз» и «снизу вверх». И вот что у меня получилось:

RC — красный, RE — синий. Ось X — количество выбранных точек. Вы думали, что «снизу вверх» может быть так же хорошо? Я так и думал, глядя на анимацию, но кажется, что сверху вниз значительно лучше (посмотрите на разреженную область). Тем не менее, не так уж ужасно, учитывая, что это намного быстрее.

Здесь я все упаковал.

http://www.filehosting.org/file/details/352267/density_sampling.tar.gz