найти (почти) минимальное накрывающее множество дисков на двумерной плоскости

Question

Хорошо, скажем, у меня есть группа дисков, сидящих на самолете в фиксированных известных местах.Каждый диск имеет радиус 1 единицу.Плоскость полностью покрыта набором дисков, фактически, она значительно перекрыта набором дисков, на порядок или два в некоторых областях.Я хотел бы найти подмножество дисков, которые все еще полностью покрывают самолет.Оптимально это хорошо, но не обязательно.

Вот предыдущая иллюстрация:

А вот следующая иллюстрация:

Кажется,Я считаю, что есть двойная проблема, связанная с триангуляцией Делоне, но я не совсем уверен, что это мне помогает.Я также знаю, что это похоже на проблему диска в вычислительной геометрии, но не совпадает с ней.Это стандартная проблема, чье имя я не знаю?

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

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

Answer 1

План игры

Ниже приведено лишь более точное изложение вашей проблемы, но оно может помочь:

1. Перечислите каждую подключенную область на плоскости, которая получается, когда границы всех дисков нарисованы. По предположению, каждая из этих областей покрыта 1 или более дисками.
2. Каждый регион - это «покрываемая вещь», а каждый диск - «покрывающая вещь». Найдите минимальный набор обложек для этого набора регионов. К сожалению, это NP-хард.

Это может не использовать всю структуру, имеющуюся в задаче, но определенно даст вам оптимальный ответ.

Перечисление регионов

Перечисление областей и запись, какие диски покрывают каждый на шаге 1, - сложная часть. Области в общем случае не выпуклые, что усложняет проверку пересечений, и каждый добавляемый круг потенциально удваивает количество областей. Вот как я мог бы подойти к этому:

Забудьте о фактическом местоположении каждого региона и определяйте регион только с точки зрения того, какие диски находятся внутри, а какие - снаружи. То есть область определяется вектором длины n со значениями 0/1, каждое из которых указывает, должна ли область внутри или снаружи этого диска быть включена в пересечение - рассматриваемая область формируется путем пересечения всех этих n областей. Таким образом, в принципе у вас может быть до 2 ^ n областей, но на практике некоторые (большинство) векторов создают пустые области, потому что они влекут за собой пересечение двух дисков, которые не имеют пересечения - это легко проверить, к счастью. Это должно быть просто для рекурсивного генерирования всех непустых областей, за исключением того, что ...

Плохие новости

К сожалению, теперь я вижу, что необходимо для полного тестирования пересечения, потому что не всегда возможно определить, когда область будет пустой. Критическим контрпримером является то, что, учитывая два диска A и B, которые имеют небольшую полосу перекрытия, и другой диск C, который перекрывает каждый из A и B, в зависимости от положения всех 3 дисков, пересечение всех 3 может или не может или не может быть непустым. (Чтобы увидеть это, нарисуйте 3 диска разных цветов с непрозрачностью 50% в программе рисования и переместите их.)

Работоспособный хак

Поскольку создание точного списка непустых областей выглядит так, как будто это будет много работы и займет много времени из-за тестирования пересечений, и вы утверждаете, что вам не нужны оптимальные решения, вы можете попробовать просто использовать сетку точек выборки как набор «вещей, которые будут покрыты» вместо точного списка непустых областей. Нетрудно определить, какие диски покрывают данную точку выборки. Затем выполните максимальное заданное покрытие, как и раньше.

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