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

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

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

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

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

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

docs.google.com/document/d/1ydAQMWJUhhRXASJnaYTTRtnMNiRKxv8mHbvhxyXC37Y/edit?hl=ru
  • Вопрос задан
  • 3271 просмотр
Пригласить эксперта
Ответы на вопрос 5
При таких порядках величин, я бы посоветовал генетические алгоритмы.

Уточните, кстати, как примерно соотносится среднее расстояние между двумя ближайшими точками (из множества 10^6) с величиной R. Без этого трудно понять, насколько плотно «заселено» Ваше пространство.
Ответ написан
Akson87
@Akson87
Не подскажу так сходу алгоритм, но попробуйте посмотреть в сторону алгоритмов для триангуляции, диаграммы Вороного и подобных, там могут быть полезные для Вас алгоритмы.
И еще вопрос, должно ли решение быть абсолютно идеальным или просто хороший результат подойдет?
Ответ написан
elDraco
@elDraco
У меня ощущение, что это очень похоже на задачу о минимальном/наименьшем покрытии. Там для множества нужно найти минимальную систему из n подмножеств (по сути множество индексов) покрывающую всё множество. В этом случае общее множество это как раз все ваши точки, круг это подмножество, а искомые индексы как раз точки, являющиеся центрами кругов. Методов решения такой задачи довольно много насколько могу судить.
Ответ написан
Комментировать
@gribozavr
Возможно, что-то можно придумать на основе поиска ближайших соседей в заданном радиусе в kd дереве.
Ответ написан
Комментировать
raptor
@raptor Автор вопроса
Порывшись в интернете с наводки хабражителя OLS, нашел наиболее подходящий под мою задачу алгоритм (семейство алгоритмов) ru.wikipedia.org/wiki/FOREL.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы