Maximal subsets of a point set which fit in a unit disk

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.

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 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.

Let's define a function $f: \Bbb R \times \Bbb R \rightarrow \left [0, n \right ] $, returning a number of points from the set $P$, covered by a unit disk with the center at the point $(x, y)$. This is a piecewise constant function, and it's easy to see that its domain can be thought as a planar subdivision, defined by all intersections of unit disks, centered at points from the set $P$. This subdivision contains vertices (= intersection points), edges (= circular arcs) and faces (= pieces of the plane, where the function $f$ returns the same value). We'll say that these faces are labeled by this value.

We'll assume that the planar graph, defined by this subdivision, is a 4-regular one - it's a common assumption, meaning that all the points in $P$ are in general position (each intersection point belongs to exactly two circles). An example of such subdivision for $n=3$ is below, where the label for each face (including the external one) is shown in red color.

As far as I understand your maximal subsets $P_i$ can be associated with such faces of this subdivision, which have labels larger than all labels of their neighboring faces. It's kind of static interpretation of your "moving disk" semantics, which you used in your definition of the maximal subset.

The subdivision will contain as many faces as possible in the case when all the unit circles pairwise intersect each other. It can be shown, that in this case:

• number of vertices is $n(n-1)$

• number of edges is $2n(n-1)$

• number of faces is $n(n-1)+2$

So, answers to your questions will be:

• No, the number $k$ of maximal subsets is $O(n^2)$, because it can't be more than the number of all faces.

• Yes, all the maximal subsets can be found in $O(n^3)$ time by naive scanning algorithm.

As for name of this problem - it looks like it may be related to some variations of the Unit Disk Cover problem.

StackExchange Computer Science Q#129390, answer score: 4