Suppose that there are a set $ P$ of $ n$ points on the plane, and let $ P_1, \dots, P_k$ be not necessarily disjoint subsets of $ P$ such that every point in $ P_i|\ 1 \leq i \leq k$ fits inside a unit disk $ D_i$ .
Moreover, each $ P_i$ is maximal. This means that if the corresponding unit disk $ D_i$ moves to cover another point, then one point which was inside the disk will be uncovered.
Here is an example:
In the above figure, there are three maximal subsets.
I don’t know whether this problem has a name or was studied before, but my question is:
- Can $ k$ be $ O(1)^n$ ?
- If not, then can we find those subsets in polynomial time w.r.t. $ n$ ?