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:

enter image description here

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:

enter image description here

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.

  • It might be interesting to note that computing the DIN may be as hard as computing a maximum independent set itself. For example, in the case of disk graphs (rather than unit disk graphs) one could add a big disk intersecting all other objects in the arrangement; computing its DIN corresponds to computing a maximum independent set in the original arrangement. – Bart Jansen Jan 27 '14 at 11:35
  • 2
    @BartJansen True, but the greedy algorithm actually doesn't need to calculate the DIN for every shape - it only needs a shape with the minimum DIN. Since the minimum DIN is at most 5 (in the case of arbitrary-sized disks), it only has to check all subsets with at most 6 disks, and see whether one of them is independent. This can be done in time $O(n^6)$ for each shape. – Erel Segal-Halevi Jan 27 '14 at 12:13
  • For your last question - yes, it is correct. – domotorp Jan 31 '14 at 19:44

What is the actual maximum minimum DIN in collections of unit-disks?

It is 3.enter image description here

  • There are 32 unit disks here, arranged in 2 levels of 16. Each disk intersects 3 disjoint disks - 2 on its own level and 1 on the other level. But, the greedy algorithm will still find an optimal solution, with 16 disks. – Erel Segal-Halevi Jan 27 '14 at 7:40
  • Yes, that answers only 1/4 of the question :-) – Yury Jan 27 '14 at 15:37

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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