Suppose that there are a set $P$ of $n$ points on the plane, and let $P_1, \dots, P_k$ be distinct subsets of $P$ such that all points in $P_i$ fits inside one unit disk for all $i$, $1\le i\le k$.
Moreover, each $P_i$ is maximal, i.e., no unit disk can cover a subset of $P$ that is a strict superset of $P_i$. Visually speaking, if we move a unit disk that covers $P_i$ to cover a point not in $P_i$, then at least one point which was inside that disk will become uncovered.
In the above figure, there are three maximal subsets.
I don't know whether this problem has a name or was studied before, but here are my questions.
- Can $k$ be exponential with respect to $n$?
- If not, then can we find those maximal subsets in polynomial time w.r.t. $n$?
I think that there are exponentially many such subsets because of the following argument:
Suppose that the points are centers of some disks with radius $1/2$. If a subset of such points fit in a unit disk, then they form a clique. Since there are exponentially many cliques in a set of disks, then there should be exponentially many maximal subsets of this particular set of points that fit into a unit disk.