Максимальные подмножества набора точек, которые помещаются в единичный диск
Предположим, что существует множество $P$ из $n$ точки на плоскости, и пусть $P_1, \dots, P_k$ быть различными подмножествами $P$ так что все точки в $P_i$ помещается в один единичный диск для всех $i$, $1\le i\le k$.
Более того, каждый $P_i$ является максимальным, т.е. ни один единичный диск не может покрыть подмножество $P$ это строгий надмножество $P_i$. Визуально говоря, если мы переместим единичный диск, покрывающий$P_i$ охватить точку не в $P_i$, то по крайней мере одна точка, которая была внутри этого диска, станет открытой.
Вот пример:
На приведенном выше рисунке есть три максимальных подмножества.
Не знаю, есть ли у этой проблемы название или изучалась она раньше, но вот мои вопросы.
- Может $k$ быть экспоненциальным по отношению к $n$?
- Если нет, то можем ли мы найти эти максимальные подмножества за полиномиальное время относительно $n$?
Я думаю, что таких подмножеств экспоненциально много из-за следующего аргумента:
предположим, что точки являются центрами некоторых дисков с радиусом$1/2$. Если подмножество таких точек помещается в единичный круг, они образуют клику. Поскольку в наборе дисков экспоненциально много клик, то должно быть экспоненциально много максимальных подмножеств этого конкретного набора точек, которые помещаются в единичный диск.
Ответы
Определим функцию $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, возвращая количество точек из множества $P$, покрытый единичным диском с центром в точке $(x, y)$. Это кусочно-постоянная функция, и легко видеть, что ее область может рассматриваться как планарное подразделение, определяемое всеми пересечениями единичных дисков с центрами в точках из множества$P$. Это подразделение содержит вершины (= точки пересечения), ребра (= дуги окружности) и грани (= части плоскости, где функция$f$возвращает то же значение). Мы скажем, что эти лица помечены этим значением.
Мы будем предполагать, что планарный граф, определяемый этим подразделением, является 4-регулярным - это обычное предположение, означающее, что все точки в $P$находятся в общем положении (каждая точка пересечения принадлежит ровно двум окружностям). Пример такого подразделения для$n=3$ внизу, где метка для каждой грани (включая внешнюю) показана красным цветом.
Насколько я понимаю ваши максимальные подмножества $P_i$могут быть связаны с такими гранями этого подразделения, у которых есть метки больше, чем все метки их соседних граней . Это своего рода статическая интерпретация семантики «движущегося диска», которую вы использовали в своем определении максимального подмножества.
Подразделение будет содержать как можно больше граней в том случае, если все единичные окружности попарно пересекаются друг с другом. Можно показать, что в этом случае:
- количество вершин $n(n-1)$
- количество ребер $2n(n-1)$
- количество лиц $n(n-1)+2$
Итак, ответы на ваши вопросы будут такими:
- Нет, номер $k$ максимальных подмножеств $O(n^2)$, потому что это не может быть больше, чем количество всех лиц.
- Да, все максимальные подмножества можно найти в $O(n^3)$ раз по наивному алгоритму сканирования.
Что касается названия этой проблемы - похоже, она может быть связана с некоторыми вариациями проблемы с крышкой блочного диска.