Pith. sign in

REVIEW 3 major objections 5 minor 18 references

Approximating the Convex Hull via Metric Space Magnitude

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Metric-space magnitude assigns each point a "moment," and the paper claims that deleting low-moment points alters the total magnitude little and leaves the convex-hull volume nearly unchanged.

desk verdict Lemma 1 and the moment ordering are real contributions, but the convex-hull guarantee in Section 3.3 fails because it conflates an integral of a max with the max of integrals. read the letter →

arxiv 1908.02692 v1 pith:ONT2CJ77 submitted 2019-08-07 math.AT

Glenn Fung , Eric Bunch , Dan Dickinson This is my paper · ORCID
classification math.AT
keywords metricspacemagnitudeweightvectorzerothmomentconvexhullapproximationfiniteEuclideanpointsetssimilaritymatrixfunction
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

This paper tries to establish that the magnitude of a finite point set—an invariant often read as the effective number of points—can be decomposed into contributions of individual points. It defines for each point a zeroth moment $\mu_0(x)=\int_0^\infty e^{-t} w_t(x)^2\,dt$, built from the weight vector of the similarity matrix of the scaled set $tX$. The central claim is that points with small moment can be removed with only a small change in magnitude, and that repeatedly removing such points yields a small subset whose convex hull has almost the same volume as the original hull. This would matter because it gives an intrinsic, pre-geometric filter for convex hull computation and other point-set reductions.

What carries the argument

The machinery is the similarity matrix $\zeta_X(i,j)=\exp(-\|x_i-x_j\|)$ for a finite set $X\subset\mathbb{R}^n$, the weight vector $w=\zeta_X^{-1}\mathbf{1}$, and the one-parameter family of scaled spaces $tX$. Lemma 1 expresses the magnitude of $X\setminus Y$ as the original magnitude minus a quadratic form in the deleted weights, with the Schur complement $\zeta_X/\zeta_{X\setminus Y}$ as the middle matrix; Proposition 2 turns that identity into a bound that only involves the number of deleted points and their largest squared weight. The zeroth moment $\mu_0(x)=\int_0^\infty e^{-t}w_t(x)^2\,dt$ removes the scale parameter and supplies the ordering used by Algorithm 1.

What would settle it

Take a finite set in $\mathbb{R}^3$ consisting of many interior Gaussian points plus a sparse layer of extreme vertices, run Algorithm 1, and compare the volume of the returned hull to the claimed $\epsilon$ bound; if a small-magnitude-error deletion causes a large volume drop, the Section 3.3 substitution is false. A cleaner check is to compute, for each $t$, the point $x_{\beta_t}$ maximizing $w_t(x)^2$ and compare it with the point $\hat{x}$ of maximal $\mu_0$; if they differ on a set where the bound is tight, the replacement of the integrated worst-case by $\mu_0(\hat{x})$ fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that the per-point entries of the weight vector $w=\zeta_X^{-1}\mathbf{1}$ carry geometric information, and that this information can be integrated over scale to form an ordering. Lemma 1 gives the exact formula $|X\setminus Y| = |X| - w_X|_Y^T (\zeta_X/\zeta_{X\setminus Y}) w_X|_Y$, and Proposition 2 bounds the loss by $|X| \ge |X\setminus Y| \ge |X| - N_Y \max_{y\in Y} w_X(y)^2$. The paper then defines the moment $\mu_0(x)$ as the scale-averaged version of $w_t(x)^2$ and argues, in the informal discussion of Section 3.3, that conditioning on the largest moment in the removed set controls the change in magnitude and, through the volume asymptotic of Theorem 6, controls the change in $\mathrm{Vol}(\mathrm{Conv}(X\setminus Y))$ relative to $\mathrm{Vol}(\mathrm{Conv}(X))$.

Load-bearing premise

The argument needs the unproved step that the volume of the scaled convex hull can be substituted for the magnitude at every scale $t$, and that the single highest-moment point can stand in for the worst-case point that changes with $t$.

Editorial extensions

If this is right

  • If the moment ordering is reliable, any exact convex hull algorithm can be preceded by a filtering step that keeps only high-moment points, cutting the input size.
  • Proposition 2 gives a quantitative guarantee on the magnitude loss: a subset $Y$ with $\max_{y\in Y} w_X(y)^2 \le \epsilon/N_Y$ can be deleted while keeping $|X\setminus Y|$ within $\epsilon$ of $|X|$.
  • Because the moment is intrinsic to the metric structure rather than to the hull's faces, the method works before the hull is known and could be used for dynamic hull maintenance.
  • The experiments suggest the filter is strong: on Gaussian clouds in $\mathbb{R}^2$ through $\mathbb{R}^5$, the average number of points needed to reach 90% of the full hull volume ranges from about 4 to about 80.

Reading between the lines

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

  • The volume guarantee in Section 3.3 is not fully proved, since it substitutes the volume asymptotics for the magnitude at all scales and replaces the worst-case point with the point of maximal moment; a numerical comparison against random subsampling would show whether the moment ordering is doing real work.
  • The moment of a point is computed from the full set's weight vector, so it changes when points are removed; Algorithm 1 does not recompute moments after deletion, and an iterative reweighting variant could behave differently.
  • Higher moments $\mu_n(x)=\int_0^\infty t^n e^{-t}w_t(x)^2\,dt$ suggest a multiscale description of each point, and could be tested as sharper filters for boundary detection.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies the magnitude of finite subsets of Euclidean space and introduces the zeroth moment mu_0(x) = integral_0^infty e^{-t} w_t(x)^2 dt as a per-point geometric score. The main formal results are Lemma 1, expressing |X\Y| in terms of the weight vector of X and a Schur complement, and Proposition 2, giving upper and lower bounds on |X\Y| in terms of the extreme point weights. Based on an informal asymptotic discussion in Section 3.3, the paper proposes Algorithm 1, which removes low-moment points and claims to approximate the convex hull volume, and reports experiments on synthetic Gaussian data in dimensions 2-5.

Significance. If the algorithmic guarantee were established, the paper would offer a novel bridge between metric magnitude and computational geometry, and the zeroth moment would be a valuable intrinsic point-ordering tool. The rigorous parts, Lemma 1 and Proposition 2, appear correct and give an explicit accounting of how deleting points affects the magnitude of a finite Euclidean set. The experiments in Section 4.3 show an empirical phenomenon worth exploring. However, the theoretical argument underpinning the central convex-hull claim contains a reversed inequality and an invalid asymptotic substitution, so the advertised guarantee is not currently supported. The paper is honest in calling Section 3.3 a discussion, but the flaw is not a matter of missing technical hypotheses; it is a logically reversed bound that cannot be repaired by epsilon-chasing within the present algorithmic framework.

major comments (3)
  1. [Section 3.3, Eq. (12) and following paragraph] The substitution of mu_0(hat x) for the integral of the time-dependent maximum has the wrong inequality direction. Since wt(x_{beta_t})^2 >= wt(x)^2 for every fixed x and every t, integrating gives integral_0^infty e^{-t} wt(x_{beta_t})^2 dt >= mu_0(x) for each x and in particular for hat x. The actual error term in the lower bound for mu_0(|tX\P|) is proportional to that integral, so bounding mu_0(hat x) by epsilon/(|P| n |X|) does not bound the true error; the true error can be arbitrarily larger when the maximizing point changes with t. Thus the claim that Algorithm 1 keeps the magnitude within a predefined threshold is not established.
  2. [Section 3.3, replacement of |tX| by Vol(Conv(X)) t^n / (n! Vol(B^n))] The replacement of |tX| by the volume-derived expression is unsupported. For finite X, Theorem 3 gives |tX| -> N as t -> infinity, so the finite-set magnitude is asymptotically constant, whereas Vol(Conv(X)) t^n / (n! Vol(B^n)) grows without bound. Theorem 6 is a statement about t Conv(X), not tX, and only in the t -> infinity limit. Because the integral defining the moment is significant over large t, the substitution used to derive the volume error bound is invalid, and the conclusion that Vol(Conv(X\P)) is within epsilon of Vol(Conv(X)) does not follow.
  3. [Section 4.1, Algorithm 1, Step 3 and the final paragraph of Section 3.3] The criterion in Algorithm 1 is written as mu_0(x_i) <= epsilon/(d_i |X|), but d_i is never defined; Section 3.3 uses epsilon/(|P| n |X|) with n unexplained. More substantively, the algorithm thresholds a per-point moment, whereas Proposition 2's error bound involves the integral of the time-dependent maximum wt(x_{beta_t})^2 over the whole set P being removed. Since the per-point moment is always a lower bound for that error integral, the algorithm's threshold cannot certify the stated magnitude or volume error, even after correcting the notation.
minor comments (5)
  1. [Section 3.3, first paragraph] The sentence claiming that a sequence {X_k} of independently sampled finite subsets of Conv(X) has monotonically increasing magnitudes |X_k| converging to |Conv(X)| is false without the subsets being nested; Theorems 4 and 5 give convergence for Hausdorff-convergent sequences, not monotonicity for arbitrary uniform samples.
  2. [Corollary 1, proof] The displayed difference mu_0(x3) - mu_0(x2) is written with the same integrand wt(x3)^2 in both integrals; the second integrand should be wt(x2)^2.
  3. [Proposition 1, proof] The line 'proving w(x3) >= w(x3)' appears to be a typo; the intended conclusion is w(x3) >= w(x2).
  4. [Section 4.2, runtime analysis] The runtime analysis counts one matrix inversion as O(n^omega), but the algorithm computes mu_0(x) for every point, which requires solving the n x n system zeta_{tX} w = 1 for many scales t and then numerically integrating over t. The analysis omits the cost of this integration and the choice of quadrature, so the stated complexity of the preprocessing step is incomplete.
  5. [Throughout] The symbol |X| is used for both the magnitude of X and the number of points in X, and Section 3.3 further proposes using |X| in place of Vol(Conv(X)). This triple overloading makes the inequalities in Section 3.3 and Algorithm 1 ambiguous.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the deletion bound is an independently proved linear-algebra statement, and the hull-volume discussion is an unsupported approximation rather than a definitional reduction.

full rationale

The paper's central formal result, Proposition 2, is derived from Lemma 1, which follows from the Schur-complement/inverse-submatrix identity, positive definiteness, and eigenvalue bounds; it does not presuppose the conclusion. The moment µ0(x) is defined as a new integral of squared weights and is not fitted to reconstruct hull volumes. Algorithm 1's criterion is tested empirically rather than derived by fitting parameters. The citations to [5], [6], [2], and [8] are to external authors and are used as background theorems. The Section 3.3 hull-volume passage contains two unjustified substitutions: 'So let us approximate |tX| with the function Vol(Conv(X)) t^n / (n! Vol(B^n))' and 'We will in practice use the value µ0(ˆx) in place of ∫ e^{-t} w_t(xβt)^2 dt.' These are real mathematical gaps, and the second substitution has the wrong inequality direction for the intended guarantee; however, they are non sequiturs or unsupported approximations, not reductions of the claimed result to its own inputs. No fitted parameter is renamed as a prediction, and no load-bearing self-citation or uniqueness import is present. The derivation chain is therefore not circular, though its hull-volume guarantee is not established by the given argument.

Assumptions & free parameters 1 free parameters · 6 assumptions · 1 invented entities

The paper depends on six results from prior work on magnitude and matrix theory, all invoked rather than proved. The only hand-chosen control parameter is the error threshold epsilon. The moment is a new definition but not an empirical fit to data.

free parameters (1)
  • epsilon (volume/magnitude error threshold) = user-specified
    Algorithm 1 step 3 returns points with moment at most epsilon/(d i |X|). Every approximation guarantee is stated in terms of this hand-chosen input, and no rule for choosing it is given.
assumptions (6)
  • domain assumption For finite X subset R^n, zeta_X and zeta_X^{-1} are symmetric positive definite (Theorem 2.5.3 of Leinster).
    Used throughout to define the weight vector and in Schur complement inequalities.
  • domain assumption The magnitude function t maps to |tX| is analytic on (0, infinity] for finite X subset R^n (Proposition 2.2.6 of Leinster).
    Justifies integrating weight functions to define the moment in Section 3.1.
  • domain assumption For finite Y subset X, 1 <= |Y| <= |X| (Corollary 2.10 of Leinster and Meckes).
    Used in Section 3.3 to argue finite subset magnitudes converge monotonically to |Conv(X)|.
  • domain assumption Magnitude is continuous under Hausdorff convergence for compact sets (Corollary 2.7 of Meckes).
    Used to treat finite samples of the convex hull as approximations of the infinite hull.
  • domain assumption For compact X, |tX|/t^n tends to Vol(X)/(n! Vol(B^n)) as t tends to infinity (Theorem 1 of Barcelo and Carbery).
    The asymptotic volume identity is the basis for replacing magnitude by hull volume in Section 3.3.
  • standard math Inverse of a principal submatrix formula (Theorem 5.1 of Ruiz et al.).
    Used in the proof of Lemma 1 to express entries of zeta_{X\Y}^{-1} in terms of zeta_X^{-1}.
invented entities (1)
  • zeroth moment of a point, mu_0(x)
    purpose: Score each point by the integral of e^{-t} w_t(x)^2 and order points for removal in Algorithm 1.
    A new mathematical descriptor introduced by the paper. Its geometric usefulness is supported only by synthetic experiments and the informal volume argument, with no external falsifiable handle.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating the Convex Hull via Metric Space Magnitude." pith.science (2026). https://pith.science/paper/ONT2CJ77

@misc{pith2026190802692,
  author       = {Pith},
  title        = {Pith review of: Approximating the Convex Hull via Metric Space Magnitude},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ONT2CJ77}},
  note         = {Machine review of arXiv:1908.02692}
}
abstract

Magnitude of a finite metric space and the related notion of magnitude functions on metric spaces is an active area of research in algebraic topology. Magnitude originally arose in the context of biology, where it represents the number of effective species in an environment; when applied to a one-parameter family of metric spaces $tX$ with scale parameter $t$, the magnitude captures much of the underlying geometry of the space. Prior work has mostly focussed on properties of magnitude in a global sense; in this paper we restrict the sets to finite subsets of Euclidean space and investigate its individual components. We give an explicit formula for the corrected inclusion-exclusion principle, and define a quantity associated with each point, called the $\textit{moment}$ which gives an intrinsic ordering to the points. We exploit this in order to form an algorithm which approximates the convex hull.

Figures

Figures reproduced from arXiv: 1908.02692 by the authors.

Figure 1
Figure 1. For each data set, the weight w is calculated. The color of a point x represents log(1 + w(x)). Synthetic data is plotted for A) Annulus B) Square C) Noisy moons D) Gaussian blobs. (td)(x, y) = td(x, y). Note that since X ⊂ R n, the metric space tX is equivalent to the metric space consisting of points whose coordinates are those of X scaled by t in each coordinate with the usual metric on R n. In this paper we will… view at source ↗
Figure 2
Figure 2. For each data set, the zeroth moment µ0(x) is calculated. The color of a point x represents log(1 + µ0(x)). Synthetic data is plotted for A) Annulus B) Square C) Noisy moons D) Gaussian blobs. Example [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Num. points Dimension Avg. # points to 90% CH volume Std. dev. points to 90% CH volume Avg. # CH ver￾tices Std. dev. # CH vertices 1000 2 4.1 1.21 12.9 2.3 1000 3 15.7 2.4 45.1 4.43 1000 4 43.35 6.32 110 10.9 1000 5 80 10.2 203 16 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Bradford Barber, David P

    C. Bradford Barber, David P. Dobkin, David P. Dobkin, and Hannu Huhdanpaa. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. , 22(4):469--483, December 1996

    work page 1996

  2. [2]

    On the magnitudes of compact sets in Euclidean spaces

    Juan Antonio Barcelo and Anthony Carbery. On the magnitudes of compact sets in Euclidean spaces . American Journal of Mathematics , 140(2):449--494, 2018

    work page 2018

  3. [3]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan. Matrix Computations . Johns Hopkins University Press, third edition edition, Oct 1996

    work page 1996

  4. [4]

    K \:u hne, and Christian Plessl

    Michael Lass, Stephan Mohr, Hendrik Wiebeler, Thomas D. K \:u hne, and Christian Plessl. A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices . Proceedings of ACM Conference , April 2017

    work page 2017

  5. [5]

    The magnitude of metric spaces

    Tom Leinster. The magnitude of metric spaces. Documenta Mathematica , 18:857–905, 2013

    work page 2013

  6. [6]

    The magnitude of a metric space: From category theory to geometric measure theory

    Tom Leinster and Mark Meckes. The magnitude of a metric space: From category theory to geometric measure theory. Aug 2018

    work page 2018

  7. [7]

    On the asymptotic magnitude of subsets of euclidean space

    Tom Leinster and Simon Willerton. On the asymptotic magnitude of subsets of euclidean space. Geometriae Dedicata , 164(1):287--310, Jun 2013

    work page 2013

  8. [8]

    M. W. Meckes. Positive definite metric spaces. Positivity , 17:733--757, Sept 2013

    work page 2013

Show all 18 references
  1. [9]

    Ju \'a rez Ruiz, R

    E. Ju \'a rez Ruiz, R. Cortes Maldonado, and Francisco Rodr \'i guez. Relationship between the inverses of a matrix and a submatrix. Computaci \'o n y Sistemas , 20, 2016

    2016

  2. [10]

    Bradford Barber, David P

    C. Bradford Barber, David P. Dobkin, David P. Dobkin, and Hannu Huh-danpaa. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw., 22(4):469–483, December 1996

    1996

  3. [11]

    Golub and Charles F

    Gene H. Golub and Charles F. Van Loan. Matrix Computations. Johns Hopkins University Press, third edition edition, Oct 1996

    1996

  4. [12]

    K uhne, and Christian Plessl

    Michael Lass, Stephan Mohr, Hendrik Wiebeler, Thomas D. K uhne, and Christian Plessl. A Massively Parallel Algorithm for the Approximate Calculation of Inverse p-th Roots of Large Sparse Matrices. Proceedings of ACM Conference, April 2017

    2017

  5. [13]

    Ju \'a rez Ruiz, R

    E. Ju \'a rez Ruiz, R. Cortes Maldonado, and Francisco Rodr \'i guez. Relationship between the inverses of a matrix and a submatrix. Computaci \'o n y Sistemas, 20, 2016

    2016

  6. [14]

    The magnitude of metric spaces

    Tom Leinster. The magnitude of metric spaces. Documenta Mathematica, 18:857–905, 2013

    2013

  7. [15]

    On the asymptotic magnitude of subsets of euclidean space

    Tom Leinster and Simon Willerton. On the asymptotic magnitude of subsets of euclidean space. Geometriae Dedicata, 164(1):287–310, Jun 2013

    2013

  8. [16]

    The magnitude of a metric space: From category theory to geometric measure theory

    Tom Leinster and Mark Meckes. The magnitude of a metric space: From category theory to geometric measure theory. arXiv:1606.00095v2 [math.MG]

    arXiv

  9. [17]

    On the magnitudes of compact sets in Euclidean spaces

    Juan Antonio Barcelo and Anthony Carbery. On the magnitudes of compact sets in Euclidean spaces. American Journal of Mathematics, 140(2):449, 2018

    2018

  10. [18]

    M. W. Meckes. Positive definite metric spaces. Positivity, 17:733

Pith tools

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