0
\$\begingroup\$

The stated assertion that a point outside some intermediate Minimum Enclosing Sphere is on the boundary of the final Minimum Enclosing Sphere seems unsupportable. It is true only for the first point removed from the point cloud and the next-to-final MES.

How does this affect the correctness of the algorithm?

Counterexample(?): 8 points of two tetrahedrons with non-overlapping circumspheres as point cloud, and perchance random sorting of points so that the vertices of the first tetrahedron are first and the vertices on the second tetrahedron last. Then the intermediate MES after last 4 encountered vertices is the circumsphere of the second tetrahedron, and the 4 points found outside that MES, which purportedly support the final MES, form the circumsphere of the first tetrahedron only.

\$\endgroup\$

1 Answer 1

0
\$\begingroup\$

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. 😜

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.