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: image of 3 maximal subsets covered by unit disks

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.

  1. Can $k$ be exponential with respect to $n$?
  2. 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.

  • $\begingroup$ If you make all $P_i$s into cliques in an undirected graph, this sounds like clique cover. $\endgroup$ – Pål GD Aug 19 '20 at 12:14
  • $\begingroup$ @Discretelizard Maximum number of maximal disks is what I'm looking for. $\endgroup$ – padawan Aug 19 '20 at 15:37
  • 1
    $\begingroup$ You can always shift your disk so that the set doesn't change and there are at least two points on the border. Since a pair of points defines 2 disks which have these points on their borders, there are at most $2 {n \choose 2} = O(n^2)$ such disks/sets. $\endgroup$ – Dmitry Aug 19 '20 at 20:57
  • 1
    $\begingroup$ Your definition of maximal subset is confusing, and your example doesn't clarify it. What about more simple and complete example? For example, two points with unit distance between them, plus one midpoint - can you please show us all your maximal subsets (with corresponding unit disks) in this case? $\endgroup$ – HEKTO Aug 30 '20 at 18:27
  • 1
    $\begingroup$ @j_random_hacker Does my edit of the question invalidate your comment? $\endgroup$ – John L. Sep 4 '20 at 22:57

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.

enter image description here

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:

  1. No, the number $k$ of maximal subsets is $O(n^2)$, because it can't be more than the number of all faces.
  2. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.