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

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

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.

  • 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 May 30 '17 at 20:40
  • 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 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 May 31 '17 at 7:45

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.

  • 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 Apr 13 at 10:43
  • 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 Apr 13 at 10:51
  • NB. It isn’t even true in general that $B\subseteq\langle MSW(L, B)\rangle$. – Robin Houston Apr 13 at 10:58
  • 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 Apr 13 at 12:47
  • 1
    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. Apr 13 at 16:58

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.