Подскажите эффективный алгоритм

Question

[raptor]

Дано множество точек на плоскости. Количество точек порядка 10^6 и больше.

Дана величина R — минимальное расстояние между точками, которые необходимо выбрать.

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

Эффективный — это с наименьшей возможной сложностью, с высокой скоростью.

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

docs.google.com/document/d/1ydAQMWJUhhRXASJnaYTTRtnMNiRKxv8mHbvhxyXC37Y/edit?hl=ru

Comments

[Kindman]

Пожалуйста, сделайте графическую иллюстрацию Вашей задачи — будет понятнее.

[raptor]

Ссылка же на иллюстрацию и ведет

Answer 1

[Андрей]

При таких порядках величин, я бы посоветовал генетические алгоритмы.

Уточните, кстати, как примерно соотносится среднее расстояние между двумя ближайшими точками (из множества 10^6) с величиной R. Без этого трудно понять, насколько плотно «заселено» Ваше пространство.

Comments

[raptor]

Точки по все плоскости в идеале до бесконечности, а R не более 2000 единиц.

[raptor]

Распределение точек на плоскости может быть различным, это могу быть скопления в разных областях, а могут быть одиночные точки.

Answer 2

[Akson87]

Не подскажу так сходу алгоритм, но попробуйте посмотреть в сторону алгоритмов для триангуляции, диаграммы Вороного и подобных, там могут быть полезные для Вас алгоритмы.
И еще вопрос, должно ли решение быть абсолютно идеальным или просто хороший результат подойдет?

Comments

[raptor]

Просто хороший результат. Полагаю для идеального решения нужно будет слишком много ресурсов.

Answer 3

[elDraco]

У меня ощущение, что это очень похоже на задачу о минимальном/наименьшем покрытии. Там для множества нужно найти минимальную систему из n подмножеств (по сути множество индексов) покрывающую всё множество. В этом случае общее множество это как раз все ваши точки, круг это подмножество, а искомые индексы как раз точки, являющиеся центрами кругов. Методов решения такой задачи довольно много насколько могу судить.

Answer 4

[gribozavr]

Возможно, что-то можно придумать на основе поиска ближайших соседей в заданном радиусе в kd дереве.

Answer 5

[raptor]

Порывшись в интернете с наводки хабражителя OLS, нашел наиболее подходящий под мою задачу алгоритм (семейство алгоритмов) ru.wikipedia.org/wiki/FOREL.