Нахождение покрытия множества точек с кружками

Question

У меня есть N точек в наборе V, заданных их координатами и числом K (0

Может кто-нибудь помочь мне с этим?

Answer 1

Эта проблема известна как (дискретная) проблема $ k $ -центра и является хорошо известной проблемой кластеризации. Хотя задача в целом является NP-полной, существует очень простой алгоритм, который генерирует решение в пределах фактора 2 оптимального решения в любой метрике (включая подразумеваемое двумерное евклидово расстояние вопроса). Это связано с Гонсалесом, и выглядит следующим образом

1. Укажите любую точку
2. Найди самого дальнего соседа
3. Найдите точку, наиболее удаленную от этих двух
4. и так далее, пока у вас не будет k очков.

Радиус R, который вы в итоге получите, является расстоянием от этой последней точки до следующей самой дальней точки. По построению вы гарантированно закроете все точки дисками радиуса с центром в каждой из k точек, и по неравенству треугольника это R будет в 2 раза больше оптимального радиуса.

Если вы знаете, что находитесь в плоскости, вы можете сделать несколько лучше в теории (в том числе получить точный алгоритм по полиному по времени от n и экспоненте от k), но на практике приведенный выше алгоритм, вероятно, будет самым простым

Answer 2

Проблема, которую вы описали, является примером более общей проблемы оптимизации, известной как проблема покрытия , которая может быть решена с помощью линейного программирования релаксации . Вы можете определить функцию стоимости, которая будет линейной по радиусу R ваших кругов (например, сумма радиусов для всех кругов), а также в переменных индикатора , которые какие точки выбраны, чтобы нарисовать круги. Эта функция стоимости будет определена с учетом ограничений, заставляющих кружки покрывать все точки в вашем наборе (см. Статью Wikipedia на LP для примеров)

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