REVIEW 3 major objections 4 minor 20 references
A Sequential Computation Algorithm for the Center of the Smallest Enclosing Ball
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A matrix recurrence for the smallest enclosing ball converges exponentially when the points are affinely independent and the circumcenter lies in the convex hull.
desk verdict A correct and clean convergence result for the affinely-independent circumcenter case, but the heuristic extension to general SEB is unproven and the experimental report is internally inconsistent. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the affine recurrence $\lambda_{N+1}=R\lambda_N+c$ with $R=I-\Omega\Phi^T\Phi$ and $c=\frac{1}{2n}\mathbf{1}-\frac{1}{2s}D\mathbf{1}$, where $\Phi=(P_1,\dots,P_n)$, $D=\mathrm{diag}(1/\|P_1\|^2,\dots,1/\|P_n\|^2)$, $s=\mathrm{tr}\,D$, and $\Omega=\frac{1}{ns}(sD-D\mathbf{1}\mathbf{1}^T D)$. It is derived by alternating minimization of a squared-error objective whose auxiliary matrix $\Theta$ plays the role of a backward channel, the same device used in channel-capacity algorithms. The load-bearing spectral facts are that $\Omega$ is positive semidefinite with one-dimensional nullspace spanned by $\mathbf{1}$, and that $\Omega\Phi^T\Phi$ has eigenvalues $0,\rho_2,\dots,\rho_n$ in $[0,1]$; hence $R$ has one eigenvalue $1$ and its remaining eigenvalues lie in $[0,1)$. The second-largest eigenvalue $\eta_2=1-\rho_2$ is the linear convergence rate and defines $\kappa=1/\ln(1/\eta_2)$.
What would settle it
Take any configuration satisfying the rank condition and compute both the limit of the recurrence and the exact smallest-enclosing-ball center by a certified finite method; if the limits differ for a configuration whose equidistant point lies in the convex hull, the main theorem and its corollary would be false. A less demanding test is the same experiment without the membership condition: for an obtuse triangle or an affine-dependent set, the bare recurrence limits to the circumcenter or to a heuristic point different from the true center, which already shows the theorem's conditions are load-bearing.
Extended reading notes
Core claim
The central claim is that the eigenvalue structure of $R=I-\Omega\Phi^T\Phi$ makes the recurrence a contraction on the affine hyperplane $\sum_i\lambda_i=1$. Under the rank condition, there is a unique equidistant point $\widetilde{Q}$ with barycentric coordinate $\widetilde{\lambda}$, and $R$ has eigenvalues $1=\eta_1>\eta_2\ge\cdots\ge\eta_n\ge0$; the eigenvector for $\eta_1$ is the all-ones vector, so the error $\lambda_N-\widetilde{\lambda}$ decays at the linear rate $\eta_2$. The paper also proves, via a standard circumcenter lemma, that $\widetilde{\lambda}$ equals the barycentric coordinate $\lambda^*$ of the smallest-enclosing-ball center whenever $\widetilde{\lambda}$ lies in $\Delta_n$, and in that case the iteration delivers $\lambda^*$ exactly. The proof uses positive semidefiniteness of $\Omega$ and the spectral relation between $\Omega\Phi^T\Phi$ and $\Omega$, so no coordinate-wise projection is needed in the rank-condition regime.
Load-bearing premise
The main theorem requires the rank condition $\mathrm{rank}(P_2-P_1,\dots,P_n-P_1)=n-1$, which forces $n\le d+1$ and affine independence, and it only delivers the smallest-enclosing-ball center when the equidistant point's barycentric coordinates are all nonnegative; the algorithm does not check that membership before declaring success.
Editorial extensions
If this is right
- For any affinely independent point set, the recurrence, starting from any $\lambda_0$ whose components sum to one, converges to the barycentric coordinate of the circumcenter, so the same code computes equidistant points without solving a linear system.
- When the circumcenter lies inside the convex hull, the algorithm returns the smallest-enclosing-ball center and its radius, with per-iteration cost $2n^2$ operations and iteration count proportional to $\ln(1/\epsilon)/\ln(1/\eta_2)$.
- The spectral-gap description gives a quantitative speed diagnosis: configurations with $\eta_2$ close to $1$ (for example, two points nearly coincident) are inherently slow for this iteration, and $\kappa$ can become arbitrarily large.
- Outside the proven regime the paper's heuristic can converge to a center that is not optimal, as its Example 5 shows, although the reported errors in radius and center are small for the tested random cases.
Reading between the lines
- An immediate testable extension is to accelerate the fixed-point iteration with momentum or Anderson mixing, using the known spectral gap as a stopping criterion; the paper itself does not explore acceleration.
- Because the rank condition restricts $n\le d+1$, the practical bottleneck is the unproven heuristic for $n>d+1$; a principled fix would be to run the recurrence only on a candidate support set whose complement is certified far from the current ball, rather than eliminating points by sign alone.
- The two-variable formulation suggests that any min-max problem expressible as minimizing a squared-distance residual over a simplex admits a similar channel-capacity-style update, with smallest enclosing ellipsoid and weighted balls as natural candidates, though the required spectral estimate would differ.
- The failure mode in the paper's Example 5 suggests that practical deployment should pair the heuristic with a final check that all points lie within the computed radius and adjust the active set if not.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an iterative algorithm for computing the barycentric coordinate of the center of the smallest enclosing ball (SEB) of n points in R^d, inspired by the Arimoto-Blahut algorithm. Under the rank condition (11), which requires n ≤ d+1 and affine independence, the paper derives a recurrence (84) and proves (Theorem 6) that it converges exponentially to the barycentric coordinate ~λ of the equidistant point ~Q, with rate governed by the second-largest eigenvalue of the matrix R. When ~λ lies in the probability simplex Δ_n, the paper invokes [10, Lemma 2] to conclude that ~λ equals the SEB center's coordinate λ*. The paper also proposes a heuristic modification for cases where the rank condition fails or ~λ ∉ Δ_n, and evaluates it numerically. The main theoretical contribution is the explicit recurrence and its convergence analysis, while the general-case guarantee rests on the heuristic.
Significance. If the theoretical result stands, it provides a simple recurrence with an explicit O(κ n^2 log(1/ε)) complexity for computing the SEB center in the restricted but nontrivial case where an equidistant point exists inside the convex hull. The derivation is self-contained, the eigenvalue analysis in Theorem 5 is coherent, and the dependence on a data-dependent constant κ is honestly stated. However, the paper's broader claim of a practical algorithm for arbitrary point sets is not supported: the rank condition excludes most instances with n > d+1, and the general-case algorithm is an unproven heuristic that the authors themselves show can fail (Example 5). The numerical evidence also contains an internal inconsistency in Example 6. The contribution is therefore a solid special-case result, but the general-case claims need substantial additional support.
major comments (3)
- [§5.2, Eqs. (79)-(81), Remark 1] The recurrence (84) is derived under the assumption that an equidistant point ~Q exists; specifically, Eq. (79) uses the identity (P_k - P_i, ~Q) = (‖P_k‖² - ‖P_i‖²)/2, which holds only when ~Q is equidistant from P_i and P_k. Remark 1 claims the recurrence is 'applicable to any Φ', but for a Φ without an equidistant point the recurrence is well-defined yet its limit has no demonstrated relation to the SEB center, and no convergence result is given for that case. This overclaim should be removed or qualified.
- [§8, Example 5] The heuristic exclusion rule is not accompanied by a proof that its fixed point solves the constrained minimization problem (34). Example 5 presents a point set (not satisfying the rank condition) on which the heuristic converges to Q∞ ≠ Q*. Since the rank condition fails for most practical inputs with n > d+1, the paper's claim of applicability to general point sets rests entirely on this unverified heuristic. The authors should either provide a rigorous analysis or clearly state that the general-case algorithm is a heuristic with no guaranteed accuracy.
- [Example 6, (i) vs. (iii)] The run time in Example 6(i) is stated to be measured until ‖λ_N - λ*‖ < 10⁻⁶, yet the reported center errors ‖Q_N - Q*‖ in (iii) are on the order of 10⁻³. Since Q_N = Φλ_N, a λ-error below 10⁻⁶ would imply a center error bounded by ‖Φ‖·10⁻⁶, which is far smaller than 10⁻³ for the unit-hypercube data. This internal inconsistency suggests either the stopping criterion is misreported, or the λ_N used in the error tables is not the same vector used for the stopping test (e.g., after renormalization on a reduced point set). The numerical evidence for the heuristic should be corrected or clarified.
minor comments (4)
- [Theorem 2] The theorem statement says 'There exist a unique equidistant point ~Q from P_1,…,P_n', but in general, an equidistant point is not unique unless the affine hull is restricted; the proof actually establishes uniqueness in the affine hull ΦL_n. The statement should specify 'unique equidistant point in ΦL_n'.
- [References] Reference [12] is given as 'Second Ed., 1985', but Horn and Johnson's Matrix Analysis second edition was published in 2013; the first edition is 1985. The bibliographic data should be corrected.
- [Example 6, tables (ii) and (iii)] The reported relative radius errors and center errors are identical to three significant digits in each case. While these quantities can be close for small errors and a radius near 1, an exact match across all four cases is suspicious and may indicate a copy-paste error in the table.
- [Conclusion] The statement that the algorithm is 'sufficiently practical' is not fully supported by the numerical comparisons, where the proposed method is slower than Welzl's method in Cases 1-4 and slower than FGK's method in Example 3. Simple implementation is a legitimate advantage, but it should be weighed against the observed performance.
Circularity Check
No circularity: the recurrence is derived from first-principles alternating minimization, its fixed point is identified with the equidistant point by algebra, and the only self-citation is non-load-bearing context.
full rationale
The paper's central derivation is self-contained and non-circular. The recurrence (84) is obtained by alternating minimization over λ∈L_n and Θ∈L_{n,d}(Q̃) (Section 5), with formulas (49) and (51) derived from Lagrange multiplier conditions; no fitted constants or target quantities are used as inputs. The fixed point of (84) is identified with the barycentric coordinate λ̃ of the equidistant point Q̃ in Lemma 4, using the linear algebra of M and the equidistance equations (26)-(32); this identification is proven, not assumed. The convergence result (Theorem 6) follows from an eigenvalue analysis of R = I - ΩΦ^TΦ (Theorem 5), which is independent of the target value λ̃. The identification λ̃ = λ* when λ̃∈Δ_n is imported from the external reference [10, Lemma 2] (FGK), not from the authors' own prior work, and it is a standard supporting-point lemma rather than a circular definition. The only self-citation, [15], appears in Section 2 as background context ('In our previous work [15], we developed a method...') and is not used in any proof or in the construction of the recurrence; hence it is not load-bearing. The heuristic algorithm of Section 8 is explicitly acknowledged to be unproven, and Example 5 demonstrates a case where it converges to a wrong center; this is a correctness limitation, not a circularity. Similarly, Example 6's reported center/radius errors around 1e-3 while the stop criterion is ||λ_N-λ*||<1e-6 is an internal-consistency concern for the numerical evidence, but again it does not indicate that any prediction reduces to an input. Overall, the paper meets the conventional benchmark of deriving its main result from stated assumptions with external support; the circularity burden is minimal.
Assumptions & free parameters
assumptions (5)
- domain assumption Rank condition (11): rank(P2-P1,...,Pn-P1) = n-1, i.e. the points are affinely independent and n <= d+1.
- domain assumption All points satisfy P_i != 0, or a translation/embedding is applied to make them so (Remark 2).
- standard math [10, Lemma 2]: if the barycentric coordinate of the equidistant point lies in the simplex Delta_n, then it equals the SEB center barycentric coordinate.
- standard math Minimax theorem (Lemma 14) used to prove Gamma = max_{lambda in Delta_n} J(lambda).
- ad hoc to paper The heuristic exclusion rule that removes any point whose barycentric coordinate becomes negative is sufficient to recover lambda* in general cases.
Cite this review
Pith. "Pith review of A Sequential Computation Algorithm for the Center of the Smallest Enclosing Ball." pith.science (2026). https://pith.science/paper/GUBLSPOQ
@misc{pith2026250600734,
author = {Pith},
title = {Pith review of: A Sequential Computation Algorithm for the Center of the Smallest Enclosing Ball},
year = {2026},
howpublished = {\url{https://pith.science/paper/GUBLSPOQ}},
note = {Machine review of arXiv:2506.00734}
}
abstract
In this paper, we consider the problem of finding the center $Q^\ast$ of the SEB (smallest enclosing ball) for $n$ points in $d$-dimensional Euclidean space. One application of the SEB is SVDD (support vector data description) in support vector machines. Our objective is to develop a sequential computation algorithm for determining the barycentric coordinate of $Q^\ast$. To achieve it, we apply the concept of the Arimoto-Blahut algorithm, which is a sequential computation algorithm used to compute the channel capacity. We first consider the case in which an equidistant point $\widetilde{Q}$ from the $n$ points exists, and construct a recurrence formula that converges to the barycentric coordinate $\widetilde{\bm\lambda}$ of $\widetilde{Q}$. When $\widetilde{Q}$ lies within the convex hull of the $n$ points, $\widetilde{Q}$ coincides with $Q^\ast$, hence in this case, the recurrence formula converges to the barycentric coordinate $\bm\lambda^\ast$ of $Q^\ast$. The resulting recurrence formula is very simple because it uses only the coordinates of the $n$ points. The computational complexity, with an approximation error of $\epsilon$ to the exact solution $\widetilde{\bm\lambda}$, is $O(\kappa n^2\log(1/\epsilon))$, where $\kappa$ is a value determined by the $n$ points. Furthermore, we modify the algorithm so that it can also be applied in cases where $\widetilde{Q}$ does not exist, and evaluate the convergence performance numerically. We compare the proposed algorithm with conventional algorithms in terms of run time and computational accuracy through several examples. The proposed algorithm has some advantages and some disadvantages compared to the conventional algorithms, but overall, since the proposed algorithm can be computed using a very simple formula, it is considered sufficiently practical.
Figures
Figures from the paper (6 more)
Reference graph
Works this paper leans on
-
[1]
Optimization algo rithms for faster computational geometry,
Allen-Zhu, Z., Liao, Z. and Yuan, Y., “Optimization algo rithms for faster computational geometry,” In 43rd Intl. Colloq. on Automata, Languages, an d Programming (ICALP 2016), LIPIcs 55, pp.53:1-53:6, 2016
work page 2016
-
[2]
An algorithm for computing the capacity of arbitrary discrete memoryless channels,
Arimoto, S., “An algorithm for computing the capacity of arbitrary discrete memoryless channels,” IEEE Trans. Inform. Theory, vol.IT-18, pp.14-2 0, 1972
work page 1972
-
[3]
Approximate c lustering via core-sets,
B˘ adoiu, M., Har-Peled, S. and Indyk, P., “Approximate c lustering via core-sets,” In Proc. STOC ’02, pp.250-257, 2002
work page 2002
-
[4]
Computation of channel capacity and rate -distortion functions,
Blahut, R.E., “Computation of channel capacity and rate -distortion functions,” IEEE Trans. Inform. Theory, vol.IT-18, pp.460-473, 1972
work page 1972
-
[5]
Sublinear o ptimization for machine learn- ing,
Clarkson, K. L., Hazan, E. and Woodruff, D. P., “Sublinear o ptimization for machine learn- ing,” J. ACM, Vol. 59, No. 6, pp.23:1-23:49, 2012
work page 2012
-
[6]
Coresets, sparse greedy approximatio n, and the Frank-Wolfe algorithm,
Clarkson, K. L., “Coresets, sparse greedy approximatio n, and the Frank-Wolfe algorithm,” ACM Trans. Algorithms, 6(4), pp. 63:1–63:30, 2010
work page 2010
-
[7]
Csisz´ ar, I. and K¨ orner, J.,Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Orlando, 1982
work page 1982
-
[8]
Information geometry and alternating minimization proce- dures
Csisz´ ar, I. and Tusn´ ady, G., “Information geometry and alternating minimization proce- dures”, Statistics and Decisions, Supplement Issue No.1, 2 05-237, 1984
work page 1984
Show all 20 references
-
[9]
Stability yields sublinear time algorithms f or geometric optimization in machine learning,
Ding, H., “Stability yields sublinear time algorithms f or geometric optimization in machine learning,” In ESA 2021, pp.38:1-38:19, 2021
2021
-
[10]
Fast smallest- enclosing-ball computation in high dimensions,
Fischer, K., G¨ artner, B. and Kutz, M., “Fast smallest- enclosing-ball computation in high dimensions,” In Algorithms – ESA 2003, LNCS 2832, pp.630-64 1, The associated computer program is available at https://github.com/hbf/miniball
2003
-
[11]
Wiley, New York, 1968
Gallager, G., Information Theory and Reliable Communication , John Wiley & Sons, New York, 1968. Wiley, New York, 1968
1968
-
[12]
Horn, R. A. and Johnson, C. R. Matrix Analysis , Cambridge University Press, Second Ed., 1985
1985
-
[13]
Mineola, New York, 2003
Karlin, S., Mathematical Methods and Theory in Games, Programming and Ec onomics, vol.I, vol.II , Dover Publications, Inc. Mineola, New York, 2003
2003
-
[14]
Appro ximate minimum enclosing balls in high dimensions using core-Sets,
Kumar, P., Mitchell, J. S. B. and Yildirim, E. A., “Appro ximate minimum enclosing balls in high dimensions using core-Sets,” J. Experimental Algorit hms, Vol.8, 2003. 32
2003
-
[15]
On the search algo rithm for the output distri- bution that achieves the channel capacity,
Nakagawa, K., Watabe K. and Sabu, T., “On the search algo rithm for the output distri- bution that achieves the channel capacity,” IEEE Trans. Inf . Theory, vol. 63, no. 2, pp. 1043-1062, Feb. 2017
2017
-
[16]
Minimum enclosing polytope in high dim ensions,
Panigrahy, R., “Minimum enclosing polytope in high dim ensions,” arXiv preprint cs/0407020, 2004
2004 arXiv
-
[17]
Quadratic Programming in Geometric O ptimization: Theory, Imple- mentation, and Applications,
Sch¨ onherr, S., “Quadratic Programming in Geometric O ptimization: Theory, Imple- mentation, and Applications,” Dissertation of Swiss Feder al Institute of Technology, http://www.inf.ethz.ch/personal/emo/DoctThesisFiles/schoenherr02.pdf
-
[18]
Support vector data desc ription,
Tax, D. M. J. and Duin, R. P. W., “Support vector data desc ription,” Machine Learning, 54, pp.45-66, 2004
2004
-
[19]
Two algorithms for the minimum enclos ing ball problem,
Yildirim, E. A., “Two algorithms for the minimum enclos ing ball problem,” SIAM J. Optim. Vol.19, No.3, pp.1368-1391, 2008
2008
-
[20]
Smallest enclosing disks (balls and ellips oids),
Welzl, E., “Smallest enclosing disks (balls and ellips oids),” In New Results and New Trends in Computer Science, LNCS 555, pp.359-370, 1991. 33
1991
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.