Consider the problem of finding a maximum disjoint set - a maximum set of non-overlapping geometric shapes, from a given collection of candidates. This is an NP-complete problem, but in many cases, the following greedy algorithm yields a constant-factor approximation:
- For every candidate shape x, calculate its disjoint intersection number $DIN(x)$ = the largest number of disjoint shapes that intersect x.
- Select a candidate shape with a smallest DIN ($\arg \min_{x} DIN(x)$). Remove it and all the shapes it intersects.
- Continue until no more candidates remain.
For example, consider the following figure from the Wikipedia page:
The green disk intersects 5 other disks, but its DIN is 3 (the 3 red disks are disjoint). The topmost and bottommost red disks intersect 2 other disks, but they themselves intersect, so their DIN is 1. The yellow disks have a DIN of 2. The greedy algorithm thus selects the topmost or the bottommost red disk.
If the minimum DIN can be bounded by a constant, then the greedy algorithm is a polynomial constant-factor approximation.
For example, if all candidate shapes are unit disks, Marathe et al (1995) show that a disk with a DIN of at most 3 always exists: the leftmost disk (the disk with the smallest x coordinate) intersects at most 3 other disjoint disks. Therefore the greedy algorithm yields a 3-approximation because it obtains 1 disk for each (at most) 3 disks in the optimal solution.
Similarly, if all candidate shapes are disks of arbitrary size, the greedy algorithm yields a 5-approximation, because the smallest disk intersects at most 5 other disjoint disks, i.e. the minimum DIN is at most 5.
So far so good, but Are these factors of 3 and 5 tight? I am not sure.
Consider the figure above. Selecting the leftmost disk (green) will find a disjoint set of size 1, which is indeed a 3-approximation to the maximum disjoint set of size 3 (red), but, the greedy algorithm will not select the green disk - it will select the top/bottom red disk, whose DIN is 1. In this case the greedy algorithm will find the optimal solution.
I couldn't find a counter-example for general $n$, in which the greedy algorithm finds a disjoint set with $n$ unit disks while the maximum disjoint set has $3n$. Actually, I couldn't even construct a general counter-example in which the minimum DIN is indeed 3. The best I could come up with is the following, in which each unit disk intersects at most 2 other disjoint disks (i.e. the minimum DIN is 2). But even here, the greedy algorithm finds the optimal solution rather than a 2-approximation:
My questions are:
- What is the actual max min DIN in collections of unit-disks? Arbitrary-sized disks?
- What is the actual approximation factor of the greedy algorithm for collections of unit-disks? For arbitrary-sized disks? (this factor is at most as large as the max min DIN, but may be smaller).
UPDATE: For every k-tuple of shapes, $x_1,...,x_k$, define $DIN(x_1,...,x_k)$ = the largest number of disjoint shapes intersected by their union $x_1\cup...\cup x_k$. Define $minDIN_k$ as the minimum DIN of over all k-tuples of disjoint shapes.
For example, in Yury's answer below, $minDIN_1=3$, because every circle intersects 3 other circles. $minDIN_2=4$, because it is possible to select 2 disjoint circles, one from the outer circle and one from the inner circle, that together intersect only 4 other circles. For every $k$, $minDIN_k\leq k+2$.
I THINK that the approximation ratio of the greedy algorithm can be bounded by $\frac{minDIN_k}{k}$, because, for every $minDIN_k$ shapes in the optimal solution, we have at least $k$ shapes in the algorithm output. Is this correct?
EDIT: I am now reading the excellent book Research problems in discrete geometry. While I haven't found this exact problem, I found a problem that looks related. In section "2.5 Thin Packings with Many Neighbors", there are examples of circle packings in which each circle touchese 5 other circles. I wonder if such a packing can yield a configuration of circles with DIN = 5.
