<p>This step of removing $X$ from $L$ before continuing recursion actually improves the algorithm, because it removes the already-added $X$ from the pool of basis candidates. It will always, provably work, because it's equivalent to the existing algorithm, and it will also work for higher dimensions.</p>

<p>Trace through the algorithm. When you use $MSW(L,B^{\prime\prime})$, there is $X \in L$ and $X \in B^{\prime\prime}$. Suppose we chose it again in step 2. Regardless of the result of step 3, $B^\prime$ will always have $X$, because the recursive function has the invariant $B \subseteq MSW(L,B)$.</p>

<p>In other words, your improvement to the algorithm shortcuts to step 3 in the part where $X$ is chosen. </p>

CC BY-SA 3.0
2018-04-13T10:43:14.687Z
It is not true that $B\subseteq MSW(L,B)$ in general. Have a look at the example linked in my comment on the question.
Robin Houston
CC BY-SA 3.0
2018-04-13T10:51:36.237Z
Neither is it true in general that $X\in B''$, for that matter! Did you mean $X\in\langle B''\rangle$? I suspect if you try to explain your argument more rigorously, you will see that it does not work.
Robin Houston
CC BY-SA 3.0
2018-04-13T10:58:05.283Z
NB. It isn’t even true in general that $B\subseteq\langle MSW(L, B)\rangle$.
Robin Houston
CC BY-SA 3.0
2018-04-13T12:47:26.360Z
I’ve added a section to the question giving a counterexample to $B\subseteq\langle MSW(L,B)\rangle$, since several people have supposed it to be true.
Robin Houston
CC BY-SA 3.0
2018-04-13T16:58:29.710Z
Oh, I totally missed that! $B^{\prime\prime} = \langle B^\prime \cup X \rangle$. Yeah, this answer is totally wrong. Should I delete it?
Larry B.
CC BY-SA 3.0
2018-04-13T16:59:59.220Z
I don’t mind! In any case I’m very grateful to you for prompting me to look at this again, and realise that I am even *more* confused than I thought I was…
Robin Houston
CC BY-SA 3.0
2018-04-12T19:22:03.260Z
2018-04-12T20:15:35.743Z
2018-04-12T20:15:35.743Z
Larry B.
<p>Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of Matoušek, Sharir and Welzl [1] to find a basis $B$ of $L$, and let $D=\langle B\rangle$, the smallest disk containing $\bigcup B$. The disk $\langle B\rangle$ may be computed algebraically using the fact that, since $B$ is a basis, each disk in $B$ is tangent to $\langle B\rangle$.</p>

<p>($B\subseteq L$ is a <em>basis</em> of $L$ if $B$ is minimal such that $\langle B\rangle=\langle L\rangle$. A basis has at most three elements; in general for balls in $\mathbb{R}^d$ a basis has at most $d+1$ elements.)</p>

<p>It is a randomised recursive algorithm as follows. (But see below for an iterative version, which may be easier to understand.)</p>

<p><strong>Procedure</strong>: $MSW(L, B)$<br>
<strong>Input</strong>: Finite sets of disks $L$, $B$, where $B$ is a basis (of $B$).</p>

<ol>
<li>If $L=\varnothing$, return $B$.</li>
<li>Otherwise choose $X\in L$ at random.</li>
<li>Let $B'\leftarrow MSW(L-\{X\}, B)$.</li>
<li>If $X\subseteq\langle B'\rangle$ then return $B'$.</li>
<li>Otherwise return $MSW(L, B'')$, where $B''$ is a basis of $B'\cup\{X\}$.</li>
</ol>

<p>Used as $MSW(L, \varnothing)$ to compute a basis of $L$.</p>

<p>Recently I had cause to implement this algorithm. After verifying that the results were correct in millions of randomly-generated test cases, I noticed that I had made an error in the implementation. In the last step I was returning $MSW(L-\{X\}, B'')$ rather than $MSW(L, B'')$.</p>

<p>Despite this error, the algorithm was giving the right answers.</p>

<p><hr>
<strong>My question:</strong> Why does this incorrect version of the algorithm apparently give correct answers here? Does it always (provably) work? If so, is that also true in higher dimensions?</p>

<p><hr></p>

<h2>Added: some misconceptions</h2>

<p>Several people have proposed incorrect arguments to the effect that the modified algorithm is trivially correct, so it may be useful to forestall some misconceptions here. One popular false belief seems to be that $B\subseteq\langle MSW(L, B)\rangle$. Here is a counterexample to that claim. Given disks $a,b,c,d,e$ as below (the boundary of $\langle a,b,e\rangle$ is also shown in red):</p>

<p><a href="https://i.sstatic.net/TuEhZ.png" rel="noreferrer"><img src="https://i.sstatic.net/TuEhZ.png" alt="Disks a, b, c, d, e"></a></p>

<p>we can have $MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$; and note that $e\notin\langle c,d\rangle$:</p>

<p><a href="https://i.sstatic.net/20NCu.png" rel="noreferrer"><img src="https://i.sstatic.net/20NCu.png" alt="the smallest enclosing circle of c and d does not contain e"></a></p>

<p>Here is how it can happen. The first observation is that $MSW(\{c\},\{a,b,e\})=\{b,c\}$:</p>

<ul>
<li>We wish to compute $MSW(\{c\},\{a,b,e\})$</li>
<li>Choose $X = c$</li>
<li>Let $B' = MSW(\varnothing, \{a,b,e\}) = \{a,b,e\}$</li>
<li>Observe that $X\notin\langle B'\rangle$</li>
<li>So let $B''$ be a basis of $B'\cup\{X\} = \{a,b,c,e\}$</li>
<li>Observe that $B''=\{b,c\}$</li>
<li>Return $MSW(\{c\}, \{b,c\})$, which is $\{b,c\}$</li>
</ul>

<p>Now consider $MSW(\{c, d\}, \{a,b,e\})$.</p>

<ul>
<li>We wish to compute $MSW(\{c, d\}, \{a,b,e\})$</li>
<li>Choose $X=d$</li>
<li>Let $B' = MSW(\{c\}, \{a,b,e\}) = \{b,c\}$</li>
<li>Observe that $X\notin\langle B'\rangle$</li>
<li>So let $B''$ be a basis of $B'\cup\{X\} = \{b,c,d\}$</li>
<li>Observe that $B''=\{c,d\}$</li>
<li>Return $MSW(\{c,d\}, \{c,d\})$, which is $\{c,d\}$</li>
</ul>

<p>(For the sake of definiteness, let us say that the disks $a,b,c,d,e$ all have radius 2, and are centred at $(30,5)$, $(30,35)$, $(10, 5)$, $(60, 26)$, and $(5, 26)$ respectively.)</p>

<p><hr></p>

<h2>Added: an iterative presentation</h2>

<p>It may be easier to think about an iterative presentation of the algorithm. I certainly find it easier to visualise its behaviour.</p>

<p><strong>Input</strong>: A list $L$ of disks<br>
<strong>Output</strong>: A basis of $L$</p>

<ol>
<li>Let $B\leftarrow\varnothing$.</li>
<li>Shuffle $L$ randomly.</li>
<li>For each $X$ in $L$:</li>
<li>&nbsp;&nbsp;If $X\notin\langle B\rangle$:</li>
<li>&nbsp;&nbsp;&nbsp;&nbsp;Let $B$ be a basis of $B\cup\{X\}$.</li>
<li>&nbsp;&nbsp;&nbsp;&nbsp;Go back to step 2.</li>
<li>Return $B$.</li>
</ol>

<p>The reason the algorithm terminates, incidentally, is that step 5 always increases the radius of $\langle B\rangle$ – and there are only finitely many possible values of $B$.</p>

<p>The modified version doesn’t have such a simple iterative presentation, as far as I can see. (I tried to give one in the previous edit to this post, but it was wrong – and gave incorrect results.)</p>

<p><hr></p>

<h3>Reference</h3>

<p>[1] Jiří Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4-5):498–516, 1996.</p>

CC BY-SA 3.0
2017-05-30T20:40:09.757Z
Firstly, in your line "Input: ..." I think you want "(of L)" rather than "(of B)". Secondly, when returning MSW(L-{X}, B'') instead of MSW(L,B''), your basis B'' is defined to be a basis of [B' union {X}] so X is still ensured to be covered by MSW(L-{X},B'') , even though you removed it from the set.
JimN
CC BY-SA 3.0
2017-05-31T07:45:35.173Z
No, I really do mean “(of B)” there, and B is not necessarily a subset of L in recursive calls. Elements of B-L are not necessarily covered by MSW(L,B), as in this example https://bl.ocks.org/robinhouston/c4c9dffbe8bd069028cad8b8760f392c where $L=\{a,b,c,d\}$ and $B=\{a,b,e\}$ (Press the little arrow buttons to step through the computation.)
Robin Houston
<cg.comp-geom><linear-programming><computational-geometry>
How not to compute the smallest circle enclosing a finite set of circles
Robin Houston
# How not to compute the smallest circle enclosing a finite set of circles

(Asked by: username_0 on 2017-05-27)

Suppose we have a finite set $L$ of disks in $\mathbb{R}^2$, and we wish to compute the smallest disk $D$ for which $\bigcup L\subseteq D$. A standard way to do this is to use the algorithm of Matoušek, Sharir and Welzl [1] to find a basis $B$ of $L$, and let $D=\langle B\rangle$, the smallest disk containing $\bigcup B$. The disk $\langle B\rangle$ may be computed algebraically using the fact that, since $B$ is a basis, each disk in $B$ is tangent to $\langle B\rangle$.

($B\subseteq L$ is a *basis* of $L$ if $B$ is minimal such that $\langle B\rangle=\langle L\rangle$. A basis has at most three elements; in general for balls in $\mathbb{R}^d$ a basis has at most $d+1$ elements.)

It is a randomised recursive algorithm as follows. (But see below for an iterative version, which may be easier to understand.)

**Procedure**: $MSW(L, B)$  
**Input**: Finite sets of disks $L$, $B$, where $B$ is a basis (of $B$).

1. If $L=\varnothing$, return $B$.
2. Otherwise choose $X\in L$ at random.
3. Let $B'\leftarrow MSW(L-\{X\}, B)$.
4. If $X\subseteq\langle B'\rangle$ then return $B'$.
5. Otherwise return $MSW(L, B'')$, where $B''$ is a basis of $B'\cup\{X\}$.

Used as $MSW(L, \varnothing)$ to compute a basis of $L$.

Recently I had cause to implement this algorithm. After verifying that the results were correct in millions of randomly-generated test cases, I noticed that I had made an error in the implementation. In the last step I was returning $MSW(L-\{X\}, B'')$ rather than $MSW(L, B'')$.

Despite this error, the algorithm was giving the right answers.

---

**My question:** Why does this incorrect version of the algorithm apparently give correct answers here? Does it always (provably) work? If so, is that also true in higher dimensions?

---

## Added: some misconceptions

Several people have proposed incorrect arguments to the effect that the modified algorithm is trivially correct, so it may be useful to forestall some misconceptions here. One popular false belief seems to be that $B\subseteq\langle MSW(L, B)\rangle$. Here is a counterexample to that claim. Given disks $a,b,c,d,e$ as below (the boundary of $\langle a,b,e\rangle$ is also shown in red):

[![Disks a, b, c, d, e](https://i.sstatic.net/TuEhZ.png)](https://i.sstatic.net/TuEhZ.png)

we can have $MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$; and note that $e\notin\langle c,d\rangle$:

[![the smallest enclosing circle of c and d does not contain e](https://i.sstatic.net/20NCu.png)](https://i.sstatic.net/20NCu.png)

Here is how it can happen. The first observation is that $MSW(\{c\},\{a,b,e\})=\{b,c\}$:

* We wish to compute $MSW(\{c\},\{a,b,e\})$
* Choose $X = c$
* Let $B' = MSW(\varnothing, \{a,b,e\}) = \{a,b,e\}$
* Observe that $X\notin\langle B'\rangle$
* So let $B''$ be a basis of $B'\cup\{X\} = \{a,b,c,e\}$
* Observe that $B''=\{b,c\}$
* Return $MSW(\{c\}, \{b,c\})$, which is $\{b,c\}$

Now consider $MSW(\{c, d\}, \{a,b,e\})$.

* We wish to compute $MSW(\{c, d\}, \{a,b,e\})$
* Choose $X=d$
* Let $B' = MSW(\{c\}, \{a,b,e\}) = \{b,c\}$
* Observe that $X\notin\langle B'\rangle$
* So let $B''$ be a basis of $B'\cup\{X\} = \{b,c,d\}$
* Observe that $B''=\{c,d\}$
* Return $MSW(\{c,d\}, \{c,d\})$, which is $\{c,d\}$

(For the sake of definiteness, let us say that the disks $a,b,c,d,e$ all have radius 2, and are centred at $(30,5)$, $(30,35)$, $(10, 5)$, $(60, 26)$, and $(5, 26)$ respectively.)

---

## Added: an iterative presentation

It may be easier to think about an iterative presentation of the algorithm. I certainly find it easier to visualise its behaviour.

**Input**: A list $L$ of disks  
**Output**: A basis of $L$

1. Let $B\leftarrow\varnothing$.
2. Shuffle $L$ randomly.
3. For each $X$ in $L$:
4. If $X\notin\langle B\rangle$:
5. Let $B$ be a basis of $B\cup\{X\}$.
6. Go back to step 2.
7. Return $B$.

The reason the algorithm terminates, incidentally, is that step 5 always increases the radius of $\langle B\rangle$ – and there are only finitely many possible values of $B$.

The modified version doesn’t have such a simple iterative presentation, as far as I can see. (I tried to give one in the previous edit to this post, but it was wrong – and gave incorrect results.)

---

### Reference

[1] Jiří Matoušek, Micha Sharir, and Emo Welzl. A subexponential bound for linear programming. Algorithmica, 16(4-5):498–516, 1996.

**Tags:** cg.comp-geom, linear-programming, computational-geometry

> **Comments:**
> **username_1**: Firstly, in your line "Input: ..." I think you want "(of L)" rather than "(of B)". Secondly, when returning MSW(L-{X}, B'') instead of MSW(L,B''), your basis B'' is defined to be a basis of [B' union {X}] so X is still ensured to be covered by MSW(L-{X},B'') , even though you removed it from the set.  
> **username_0**: No, I really do mean “(of B)” there, and B is not necessarily a subset of L in recursive calls. Elements of B-L are not necessarily covered by MSW(L,B), as in this example https://bl.ocks.org/robinhouston/c4c9dffbe8bd069028cad8b8760f392c where $L=\{a,b,c,d\}$ and $B=\{a,b,e\}$ (Press the little arrow buttons to step through the computation.)  

---

## 1 answers

### Answer by username_2 on 2018-04-12. Score: 1

This step of removing $X$ from $L$ before continuing recursion actually improves the algorithm, because it removes the already-added $X$ from the pool of basis candidates. It will always, provably work, because it's equivalent to the existing algorithm, and it will also work for higher dimensions.

Trace through the algorithm. When you use $MSW(L,B^{\prime\prime})$, there is $X \in L$ and $X \in B^{\prime\prime}$. Suppose we chose it again in step 2. Regardless of the result of step 3, $B^\prime$ will always have $X$, because the recursive function has the invariant $B \subseteq MSW(L,B)$.

In other words, your improvement to the algorithm shortcuts to step 3 in the part where $X$ is chosen.

> **Comments:**
> **username_0**: It is not true that $B\subseteq MSW(L,B)$ in general. Have a look at the example linked in my comment on the question.  
> **username_0**: Neither is it true in general that $X\in B''$, for that matter! Did you mean $X\in\langle B''\rangle$? I suspect if you try to explain your argument more rigorously, you will see that it does not work.  
> **username_0**: NB. It isn’t even true in general that $B\subseteq\langle MSW(L, B)\rangle$.  
> **username_0**: I’ve added a section to the question giving a counterexample to $B\subseteq\langle MSW(L,B)\rangle$, since several people have supposed it to be true.  
> **username_2**: Oh, I totally missed that! $B^{\prime\prime} = \langle B^\prime \cup X \rangle$. Yeah, this answer is totally wrong. Should I delete it?  
> **username_0**: I don’t mind! In any case I’m very grateful to you for prompting me to look at this again, and realise that I am even *more* confused than I thought I was…  

---

