Pith. sign in

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 →

arxiv 2506.00734 v1 pith:GUBLSPOQ submitted 2025-05-31 cs.IT math.IT

classification cs.ITmath.IT
keywords smallestenclosingballbarycentriccoordinatesequentialcomputationalgorithmequidistantpointcircumcenterchannel-capacityalternatingminimizationlinearconvergencecomputationalcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper's goal is a sequential algorithm that produces the center of the smallest enclosing ball from the barycentric coordinates of the $n$ given points. It adapts the alternating-minimization scheme used to compute channel capacity to the geometric min-max problem, obtaining the fixed-point update $\lambda_{N+1}=R\lambda_N+c$ whose matrices are built only from the point coordinates. The main theorem says that when the shifted points are affinely independent, the iterates converge exponentially to the barycentric coordinate of the unique point equidistant from all $n$ points; when that equidistant point lies in the convex hull, it is the center of the smallest enclosing ball, so the same iteration solves the problem. The paper states the complexity to reach error $\epsilon$ as $O(\kappa n^2\log(1/\epsilon))$, with $\kappa$ determined by the spectral gap of $R$. For configurations outside the rank condition, the paper proposes a heuristic point-removal modification and presents numerical evidence that it is often accurate but not always.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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)
  1. [§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.
  2. [§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.
  3. [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)
  1. [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'.
  2. [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.
  3. [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.
  4. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 5 assumptions · 0 invented entities

No new physical or mathematical entities are introduced, and the recurrence has no fitted free parameters. The main unstated load is the rank condition restricting the guaranteed regime, and the ad-hoc exclusion heuristic for the general case.

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.
    Used in Lemma 1, Theorem 2, Theorems 5 and 6 to guarantee existence and uniqueness of the equidistant point and of the barycentric coordinate. Without it, the main convergence theorem does not apply.
  • domain assumption All points satisfy P_i != 0, or a translation/embedding is applied to make them so (Remark 2).
    The recurrence uses 1/||P_i||^2, so P_i = 0 must be avoided; the paper suggests adding a constant coordinate.
  • 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.
    Cited from prior work, used in Remark 3 to connect convergence to tilde_lambda with the SEB center.
  • standard math Minimax theorem (Lemma 14) used to prove Gamma = max_{lambda in Delta_n} J(lambda).
    Applied in Appendix A to prove Theorem 1, a known result for the SEB formulation.
  • 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.
    Proposed in Section 8 without proof; Example 5 shows it can fail, so this is an unsupported assumption underlying the practical claims.

how reviews work

0 comments
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 reproduced from arXiv: 2506.00734 by the authors.

Figure 1
Figure 1. △P 1P 2P 3 is an acute triangle. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. △P 1P 2P 3 is an obtuse triangle. Q∗ P 1 P 2 P 3 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Three points P 1 , P2 , P3 are collinear. In the above cases, in (i) and (ii), we have rank (P 2 − P 1 , P3 − P 1 ) = 2, and in (iii), rank (P 2 − P 1 , P3 − P 1 ) = 1. 3.4 Rank Condition Consider the case where the points P 1 , . . . , P n are in general position, meaning that rank P 2 − P 1 , . . . , P n − P 1  = n − 1 (11) holds. We refer to this condition as the rank condition. Under the rank condition (11), we… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: The convergence rate of λ N → λ ∗ in Example 3 for n = 29. In this example 3, since λ ∗ = λe, we can compare the proposed method with other conven￾tional methods. We will compare below the run time of the proposed method with that of Welzl’s method [20] and FGK’s metho…
Figure 5
Figure 5. Figure 5: Run time comparison with Welzl’s Method [20]. [PITH_FULL_IMAGE:figures/full_fig_p026_5.png]
Figure 6
Figure 6. Figure 6: Run time comparison with FGK’s Method [10] [PITH_FULL_IMAGE:figures/full_fig_p026_6.png]
Figure 7
Figure 7. Figure 7: Heuristic Algorithm 9 Numerical Examples (2) We have applied the heuristic algorithm for several Φ’s, then there were cases where the correct λ ∗ was obtained and cases where it was not. Below, we present the case where the correct λ ∗ was obtained as Example 4 and the…
Figure 8
Figure 8. Figure 8: But the difference between Q∞ and Q∗ is very small, so the heuristic algorithm can still be considered a practical approximation. Q∗ = t (−0.011416, −0.040841) Q∞ = t (−0.014318, −0.044562) P 1 P 2 P 3 P 4 [PITH_FULL_IMAGE:figures/full_fig_p028_8.png]
Figure 9
Figure 9. Figure 9: Positions of P 1 , P2 , P3 . The matrix Φ satisfies the rank condition (11). Furthermore, since the triangle △P 1P 2P 3 is acute, we have λe ∈ ∆3 , and thus λ ∗ = λe. Therefore, it follows from Theorem 6 that λ N → λ ∗ as N → ∞. Now, consider the eigenvalues ρ2, ρ3 of …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [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

  7. [7]

    and K¨ orner, J.,Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Orlando, 1982

    Csisz´ ar, I. and K¨ orner, J.,Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Orlando, 1982

  8. [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

Show all 20 references
  1. [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

  2. [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

  3. [11]

    Wiley, New York, 1968

    Gallager, G., Information Theory and Reliable Communication , John Wiley & Sons, New York, 1968. Wiley, New York, 1968

  4. [12]

    Horn, R. A. and Johnson, C. R. Matrix Analysis , Cambridge University Press, Second Ed., 1985

  5. [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

  6. [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

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

  8. [16]

    Minimum enclosing polytope in high dim ensions,

    Panigrahy, R., “Minimum enclosing polytope in high dim ensions,” arXiv preprint cs/0407020, 2004

  9. [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

  10. [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

  11. [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

  12. [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

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.