Return to Answer

It sounds like you've slightly misunderstood Welzl's minimum enclosing sphere algorithm.

It does not claim that a point \$P_k\$ outside an intermediate Minimum Enclosing Sphere of points \$P_1-P_{k-1}\$ must be on the boundary of the final sphere.

It says that in that case, \$P_k\$ must be on the boundary of the Minimum Enclosing Sphere of points \$P_1 - P_k\$, which is a significantly less demanding claim. It may or may not be on the boundary of the minimum enclosing sphere of points \$P_1 - P_n\$ for \$n > k\$ — the algorithm makes no assumption about this.

This means if we chose any sphere to bound \$P_1 - P_k\$ for which \$P_k\$ is in its interior, then we expanded our sphere "too far" - we overshot \$P_k\$ and included some empty space on the far side of it. If we backtrack a bit, shrinking our sphere to exclude that empty space while keeping all points \$P_1 - P_k\$ covered, we'll eventually hit a point where the boundary hits \$P_k\$.

The smallest sphere covering all points \$P_1-P_k\$ with \$P_k\$ on its boundary is necessarily smaller than any alternative sphere containing the same points with \$P_k\$ in its interior (given that \$P_k\$ is not in \$\text{MES}(P_1-P_{k-1})\$)

I have a C# implementation of the algorithm written up in this answer. You can see how the boundary points chosen by the algorithm apply to deeper recursive calls, but don't bubble up to the parent calls from earlier in the tree.

Another way to think of this is to reflect on the fact that this is a dynamic programming algorithm, meaning it exploits optimal substructure: The optimum solution to some problem of size \$n\$ is built out of solutions to sub-problems of size \$k < n\$. That means if you agree an assumption is valid for the final step of the algorithm, it must be valid for all steps before that too. Why? Because the second-last step of the algorithm is itself the "final step" of the algorithm when running on some smaller data set, and we already conceded that the assumption is valid for the final step. QED. 😜

It sounds like you've slightly misunderstood Welzl's minimum enclosing sphere algorithm.

It does not claim that a point \$P_k\$ outside an intermediate Minimum Enclosing Sphere of points \$P_1-P_{k-1}\$ must be on the boundary of the final sphere.

It says that such a point must be on the boundary of the minimum enclosing sphere of points \$P_1 - P_k\$, which is a significantly less demanding claim. It may or may not be on the boundary of the minimum enclosing sphere of points \$P_1 - P_n\$ for \$n > k\$ — the algorithm makes no assumption about this.

This means if we chose any sphere to enclose \$P_1 - P_k\$ for which \$P_k\$ is in its interior, then we expanded our sphere "too far" - we overshot \$P_k\$ and included some empty space on the far side of it. If we backtrack a bit, shrinking our sphere to exclude that empty space while keeping all points \$P_1 - P_k\$ covered, we'll eventually hit a point where the boundary hits \$P_k\$.

The smallest sphere enclosing all points \$P_1-P_k\$ with \$P_k\$ on its boundary is necessarily smaller than any alternative sphere containing the same points with \$P_k\$ in its interior (given that \$P_k\$ is not in \$\text{MES}(P_1-P_{k-1})\$)

I have a C# implementation of the algorithm written up in this answer. You can see how the boundary points chosen by the algorithm apply to deeper recursive calls, but don't bubble up to the parent calls from earlier in the tree.

Another way to think of this is to reflect on the fact that this is a dynamic programming algorithm, meaning it exploits optimal substructure: The optimum solution to some problem of size \$n\$ is built out of solutions to sub-problems of size \$k < n\$. That means if you agree an assumption is valid for the final step of the algorithm, it must be valid for all steps before that too. Why? Because the second-last step of the algorithm is itself the "final step" of the algorithm when running on some smaller data set, and we already conceded that the assumption is valid for the final step. QED. 😜

It sounds like you've slightly misunderstood Welzl's minimum enclosing sphere algorithm.

It does not claim that a point \$P_k\$ outside an intermediate Minimum Enclosing Sphere of points \$P_1-P_{k-1}\$ must be on the boundary of the final sphere.

It says that in that case, \$P_k\$ must be on the boundary of the Minimum Enclosing Sphere of points \$P_1 - P_k\$, which is a significantly less demanding claim. It may or may not be on the boundary of the minimum enclosing sphere of points \$P_1 - P_n\$ for \$n > k\$ — the algorithm makes no assumption about this.

This means if we chose any sphere to bound \$P_1 - P_k\$ for which \$P_k\$ is in its interior, then we expanded our sphere "too far" - we overshot \$P_k\$ and included some empty space on the far side of it. If we backtrack a bit, shrinking our sphere to exclude that empty space while keeping all points \$P_1 - P_k\$ covered, we'll eventually hit a point where the boundary hits \$P_k\$.

The smallest sphere covering all points \$P_1-P_k\$ with \$P_k\$ on its boundary is necessarily smaller than any alternative sphere containing the same points with \$P_k\$ on its interior (if \$P_k\$ is not in \$MES(P_1-P_{k-1})\$)

I have a C# implementation of the algorithm written up in this answer. You can see how the boundary points chosen by the algorithm apply to deeper recursive calls, but don't bubble up to the parent calls from earlier in the tree.

Another way to think of this is to reflect on the fact that this is a dynamic programming algorithm, meaning it exploits optimal substructure: The optimum solution to some problem of size \$n\$ is built out of solutions to sub-problems of size \$k < n\$. That means if you agree an assumption is valid for the final step of the algorithm, it must be valid for all steps before that too. Why? Because the second-last step of the algorithm is itself the "final step" of the algorithm when running on some smaller data set, and we already conceded that the assumption is valid for the final step. QED. 😜

It sounds like you've slightly misunderstood Welzl's minimum enclosing sphere algorithm.

It does not claim that a point \$P_k\$ outside an intermediate Minimum Enclosing Sphere of points \$P_1-P_{k-1}\$ must be on the boundary of the final sphere.

It says that in that case, \$P_k\$ must be on the boundary of the Minimum Enclosing Sphere of points \$P_1 - P_k\$, which is a significantly less demanding claim. It may or may not be on the boundary of the minimum enclosing sphere of points \$P_1 - P_n\$ for \$n > k\$ — the algorithm makes no assumption about this.

This means if we chose any sphere to bound \$P_1 - P_k\$ for which \$P_k\$ is in its interior, then we expanded our sphere "too far" - we overshot \$P_k\$ and included some empty space on the far side of it. If we backtrack a bit, shrinking our sphere to exclude that empty space while keeping all points \$P_1 - P_k\$ covered, we'll eventually hit a point where the boundary hits \$P_k\$.

The smallest sphere covering all points \$P_1-P_k\$ with \$P_k\$ on its boundary is necessarily smaller than any alternative sphere containing the same points with \$P_k\$ in its interior (given that \$P_k\$ is not in \$\text{MES}(P_1-P_{k-1})\$)

I have a C# implementation of the algorithm written up in this answer. You can see how the boundary points chosen by the algorithm apply to deeper recursive calls, but don't bubble up to the parent calls from earlier in the tree.

Another way to think of this is to reflect on the fact that this is a dynamic programming algorithm, meaning it exploits optimal substructure: The optimum solution to some problem of size \$n\$ is built out of solutions to sub-problems of size \$k < n\$. That means if you agree an assumption is valid for the final step of the algorithm, it must be valid for all steps before that too. Why? Because the second-last step of the algorithm is itself the "final step" of the algorithm when running on some smaller data set, and we already conceded that the assumption is valid for the final step. QED. 😜

It sounds like you've slightly misunderstood Welzl's minimum enclosing sphere algorithm.

It does not claim that a point \$P_k\$ outside an intermediate Minimum Enclosing Sphere of points \$P_1-P_{k-1}\$ must be on the boundary of the final sphere.

It says that in that case, \$P_k\$ must be on the boundary of the Minimum Enclosing Sphere of points \$P_1 - P_k\$, which is a significantly less demanding claim. It may or may not be on the boundary of the minimum enclosing sphere of points \$P_1 - P_n\$ for \$n > k\$ — the algorithm makes no assumption about this.

This means if we chose any sphere to bound \$P_1 - P_k\$ for which \$P_k\$ is in its interior, then we expanded our sphere "too far" - we overshot \$P_k\$ and included some empty space on the far side of it. If we backtrack a bit, shrinking our sphere to exclude that empty space while keeping all points \$P_1 - P_k\$ covered, we'll eventually hit a point where the boundary hits \$P_k\$.

The smallest sphere covering all points \$P_1-P_k\$ with \$P_k\$ on its boundary is necessarily smaller than any alternative sphere containing the same points with \$P_k\$ on its interior (if \$P_k\$ is not in \$MES(P_1-P_{k-1})\$)

I have a C# implementation of the algorithm written up in this answer. You can see how the boundary points chosen by the algorithm apply to deeper recursive calls, but don't bubble up to the parent calls from earlier in the tree.

It sounds like you've slightly misunderstood Welzl's minimum enclosing sphere algorithm.

It does not claim that a point \$P_k\$ outside an intermediate Minimum Enclosing Sphere of points \$P_1-P_{k-1}\$ must be on the boundary of the final sphere.

It says that in that case, \$P_k\$ must be on the boundary of the Minimum Enclosing Sphere of points \$P_1 - P_k\$, which is a significantly less demanding claim. It may or may not be on the boundary of the minimum enclosing sphere of points \$P_1 - P_n\$ for \$n > k\$ — the algorithm makes no assumption about this.

This means if we chose any sphere to bound \$P_1 - P_k\$ for which \$P_k\$ is in its interior, then we expanded our sphere "too far" - we overshot \$P_k\$ and included some empty space on the far side of it. If we backtrack a bit, shrinking our sphere to exclude that empty space while keeping all points \$P_1 - P_k\$ covered, we'll eventually hit a point where the boundary hits \$P_k\$.

The smallest sphere covering all points \$P_1-P_k\$ with \$P_k\$ on its boundary is necessarily smaller than any alternative sphere containing the same points with \$P_k\$ on its interior (if \$P_k\$ is not in \$MES(P_1-P_{k-1})\$)

I have a C# implementation of the algorithm written up in this answer. You can see how the boundary points chosen by the algorithm apply to deeper recursive calls, but don't bubble up to the parent calls from earlier in the tree.

Another way to think of this is to reflect on the fact that this is a dynamic programming algorithm, meaning it exploits optimal substructure: The optimum solution to some problem of size \$n\$ is built out of solutions to sub-problems of size \$k < n\$. That means if you agree an assumption is valid for the final step of the algorithm, it must be valid for all steps before that too. Why? Because the second-last step of the algorithm is itself the "final step" of the algorithm when running on some smaller data set, and we already conceded that the assumption is valid for the final step. QED. 😜