<blockquote>
  <p>What is the actual maximum minimum DIN in collections of unit-disks?</p>
</blockquote>

<p>It is 3.<img src="https://i.sstatic.net/rtIeC.png" alt="enter image description here"></p>

CC BY-SA 3.0
2014-01-27T07:40:07.097Z
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
CC BY-SA 3.0
2014-01-27T15:37:18.540Z
Yes, that answers only 1/4 of the question :-)
Yury
CC BY-SA 3.0
2014-01-26T21:01:39.330Z
2014-01-26T21:01:39.330Z
Yury
<p>Consider the problem of finding a <a href="https://en.wikipedia.org/wiki/Maximum_disjoint_set" rel="nofollow noreferrer">maximum disjoint set</a> - 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:</p>

<ul>
<li>For every candidate shape <em>x</em>, calculate its <em>disjoint intersection number</em> $DIN(x)$ = the largest number of disjoint shapes that intersect <em>x</em>.</li>
<li>Select a candidate shape with a smallest DIN ($\arg \min_{x} DIN(x)$). Remove it and all the shapes it intersects.</li>
<li>Continue until no more candidates remain.</li>
</ul>

<p>For example, consider the following figure from the Wikipedia page:</p>

<p><img src="https://i.sstatic.net/XhekH.png" alt="enter image description here"></p>

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

<p>If the minimum DIN can be bounded by a constant, then the greedy algorithm is a polynomial constant-factor approximation.</p>

<p>For example, if all candidate shapes are unit disks, <a href="http://dx.doi.org/10.1002/net.3230250205" rel="nofollow noreferrer">Marathe et al (1995)</a> show that a disk with a DIN of at most 3 always exists: the <em>leftmost</em> 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.</p>

<p>Similarly, if all candidate shapes are disks of arbitrary size, the greedy algorithm yields a 5-approximation, because the <em>smallest</em> disk intersects at most 5 other disjoint disks, i.e. the minimum DIN is at most 5.</p>

<p>So far so good, but <strong>Are these factors of 3 and 5 tight?</strong> I am not sure.</p>

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

<p>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:</p>

<p><img src="https://i.sstatic.net/jpIiH.png" alt="enter image description here"></p>

<p>My questions are:</p>

<ul>
<li>What is the <em>actual</em> max min DIN in collections of unit-disks? Arbitrary-sized disks? </li>
<li>What is the <em>actual</em> 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).</li>
</ul>

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

<p>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$. </p>

<p>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?</p>

<p>EDIT: I am now reading the excellent book <a href="http://www.springer.com/gp/book/9780387238159" rel="nofollow noreferrer">Research problems in discrete geometry</a>. 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.</p>

CC BY-SA 3.0
2014-01-27T11:35:31.793Z
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
CC BY-SA 3.0
2014-01-27T12:13:28.503Z
@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
CC BY-SA 3.0
2014-01-31T19:44:15.040Z
For your last question - yes, it is correct.
domotorp
<cg.comp-geom>
Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?
Erel Segal-Halevi
# Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?

(Asked by: username_0 on 2014-01-26)

Consider the problem of finding a [maximum disjoint set](https://en.wikipedia.org/wiki/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](https://i.sstatic.net/XhekH.png)

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)](http://dx.doi.org/10.1002/net.3230250205) 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](https://i.sstatic.net/jpIiH.png)

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](http://www.springer.com/gp/book/9780387238159). 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.

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: For your last question - yes, it is correct.  

---

## 1 answers

### Answer by username_3 on 2014-01-26. Score: 19

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

It is 3.![enter image description here](https://i.sstatic.net/rtIeC.png)

> **Comments:**
> **username_0**: 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.  
> **username_3**: Yes, that answers only 1/4 of the question :-)  

---

