Pith. sign in

REVIEW 2 major objections 4 minor 19 references

This paper establishes a deterministic algorithm that computes a (1+ε)-approximation to the minimum spanning tree of an n-point doubling metric in time 2^{O(ddim)} n (log n + ε^{-1} log^4(1/ε)).

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 05:51 UTC pith:YUUS5QT5

load-bearing objection Main theorem holds; a real epsilon-dependence improvement with two minor proof gaps that need a quick fix. the 2 major comments →

arxiv 2607.13284 v1 pith:YUUS5QT5 submitted 2026-07-14 cs.DS

A Fast and Simple (1+ε)-Approximation for Minimum Spanning Trees in Doubling Metrics

Jan H\"ockendorff , Felix Hommelsheim , Christian Sohler , Di Yue This is my paper
classification cs.DS MSC 68W2568U0505C85
keywords minimum spanning treedoubling dimensionapproximation algorithmnet hierarchywell-separated pair covermultiscale lower boundEuclidean MSTdeterministic algorithm
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper proves that a (1+ε)-approximate minimum spanning tree of an n-point metric space with bounded doubling dimension can be computed deterministically in time 2^{O(ddim)} n (log n + ε^{-1} log^4(1/ε)). The algorithm improves the earlier ε^{-O(ddim)} dependence to essentially linear in 1/ε, and for bounded-dimensional Euclidean inputs it also improves the previous best deterministic running time by nearly a factor of 1/ε. The approach uses a hierarchical net structure and a relaxed well-separated pair cover, charging the approximation error to a multiscale lower bound on the MST. The paper also shows that MST degree can be unbounded in doubling metrics, yet every doubling metric still admits a (1+ε)-approximate MST of degree 2^{O(ddim)} log(1/ε).

Core claim

The central claim is that the MST of a doubling metric can be approximated to within 1+ε in time that depends only linearly on 1/ε (up to log factors) instead of the previous ε^{-O(ddim)}. The proof pairs a well-separated pair cover built on nested nets with a single "critical level" ℓ* that maximizes 2^{ℓ/2}|N_ℓ|, which certifies the MST weight. Levels far below ℓ* need only crude center-to-center edges; levels near ℓ* use a bounded-depth net refinement; levels far above ℓ* permit refining searches whose cost is justified because the number of net points decreases geometrically. Summing the approximation error over these three regimes, charged to the optimum MST via a packing lemma, gives a

What carries the argument

The well-separated pair cover (WSPC): a relaxed analogue of a well-separated pair decomposition where every pair of points is covered by at least one well-separated pair of clusters, but overlap is allowed. Built from a nested net hierarchy (N_0 = X ⊇ N_1 ⊇ ... ⊇ N_L) with each N_ℓ a 2^{ℓ-3}-packing, 2^{ℓ-2}-covering net, the WSPC pairs have bounded level difference and bounded per-point degree. The quantity ℓ* = argmax 2^{ℓ/2}|N_ℓ| is the key guide: it dictates how accurately each scale must be processed, and the algorithm opts for crude centers below ℓ*, accurate refinement near ℓ*, and increasingly refined searches above ℓ*.

Load-bearing premise

The load-bearing premise is that the well-separated pair cover of Lemma 2.11 — a collection of pairs of net points with bounded level difference, 32-separation, covering, and per-net-point degree t^{O(ddim)} — can be constructed in t^{O(ddim)} n log Δ time; if this cover is impossible or too dense for some doubling metric, both the error charging and the near-linear time bound of Theorem 1.1 collapse.

What would settle it

A concrete test: take a family of doubling metrics with n points and aspect ratio Δ (for instance, random points in the unit square), and run the net-based WSPC construction from Lemma 2.11 with t=32. If the maximum number of pairs per net point grows with n (rather than staying bounded by 32^{O(ddim)}), then the bounded-degree property (4) fails, and the running-time analysis of Section 3.3 would break for those instances.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • A deterministic (1+ε)-approximation for MST in doubling metrics runs in 2^{O(ddim)} n (log n + ε^{-1} log^4(1/ε)).
  • For bounded doubling dimension, the exponential-in-dimension dependence on ε is replaced by an essentially linear dependence on 1/ε.
  • For Euclidean metrics of fixed dimension, this improves the previous best deterministic running time by roughly a factor of 1/ε.
  • There exist metrics of bounded doubling dimension whose MST has maximum degree Ω(n), so degree-based structural arguments from Euclidean MSTs do not carry over.
  • Every doubling metric admits a (1+ε)-approximate MST with maximum degree 2^{O(ddim)} log(1/ε).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The critical-level argument that selects the strongest net-induced lower bound may be portable to other near-linear-time approximation problems on doubling metrics, such as approximate shortest-path trees or matching, where multiscale lower bounds can be charged similarly.
  • A testable extension is to replace the well-separated pair cover with a truly sparse WSPD, if one exists with bounded degree; this could remove the log n term in the running time, a question the paper leaves open.
  • The degree-bound result suggests that random sampling or local-search heuristics for MST in low-dimensional metric data can restrict to bounded-degree trees without sacrificing the (1+ε) approximation, which may be useful in streaming or parallel settings.
  • The separation of scales into a single critical window is reminiscent of kernelization in parameterized algorithms; the same principle might apply to other hierarchical decomposition techniques.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper presents a deterministic algorithm that, given an n-point metric space of doubling dimension ddim, computes a (1+ε)-approximate MST in time 2^{O(ddim)} n (log n + ε^{-1} log^4(1/ε)). The algorithm constructs a net hierarchy and a well-separated pair cover, identifies a level ℓ* that maximizes 2^{ℓ/2}|N_ℓ| as a lower-bound certificate, and then processes cover pairs at low, middle, and high levels with different closest-pair refinement accuracies. The approximation analysis charges the resulting error to lower bounds derived from packing/covering properties, and the time analysis balances the number of pairs against the threshold parameters γ and τ_ℓ. The paper also proves two structural results: bounded-doubling metrics can have MSTs of unbounded maximum degree, yet always admit a (1+ε)-approximate MST of maximum degree 2^{O(ddim)} log(1/ε).

Significance. The main theorem, if correct, is a substantial improvement: for bounded doubling dimension it replaces the previous deterministic ε^{-O(ddim)} dependence by an essentially linear ε^{-1} dependence, and it improves the deterministic Euclidean result of Arya–Mount by nearly a factor of 1/ε. The multiscale charging argument is elegant and self-contained, and the degree results are of independent interest. I find the central claim substantively sound; the proof has a few local rigor gaps that are repairable without changing the algorithm or the bounds. I also note that the proof does not rely on fitted parameters or circular assumptions, and the net-hierarchy/WSPC constructions are given in detail rather than deferred to folklore.

major comments (2)
  1. [Section 3.2, middle-level error bound (before Eq. (5))] The summation step from a sum over unordered pairs of (f(u)+f(v)) to a sum over u of f(u)·|{v:(u,v)∈Ψ}| is almost correct, because the second sum includes both endpoints of a pair when both levels lie in the summation range. However, there is a genuine boundary omission: a middle-level pair with max level exactly ℓ*−10 log(1/ε) can have its other endpoint at level ℓ*−10 log(1/ε)−1, which falls outside the subsequent level sum. The proof should extend the summation one level downward or absorb this boundary contribution into the low-level error estimate. This is a local fix and does not affect the asymptotic claim.
  2. [Section 3.2, proof of Lemma 3.1, definition of Φ′] The claim that Φ′ is a 7-WSPC is not justified as written for level-0 pairs. The proof says that if a covering pair (u,v) has lev(u)=lev(v)=0, then the singleton pair ({u},{v}) covers the original points x,y, since x∈B(u,1) and y∈B(v,1). But B(u,1) may contain points other than u, so an arbitrary covering pair from Lemma 2.11(3) does not guarantee x=u and y=v. The repair is to use the specific pair produced by the descent in Lemma 2.11: for two distinct original points, if no separated pair is found at higher levels, the recursion terminates at level 0 with the points themselves, so the level-0 covering pair has exactly u=x and v=y. This should be stated explicitly.
minor comments (4)
  1. [Section 2.3 / Lemma B.2] The aspect-ratio reduction is written as 'n^{10}/ε' in some places, which can be visually confused with 'n^{10/ε}'. Please typeset it unambiguously, e.g., n^{10}/\epsilon.
  2. [Algorithm 1, lines 9 and 13] For k=0 the notation D_{lev(u)}(u) is not defined by Definition 2.5, since descendants are only defined for strictly lower levels. Please either define D_{lev(u)}(u)=\{u\} or phrase the search as starting from k=1 with k=0 meaning no refinement.
  3. [Section 3.2, high-level error bound] In the high-level analysis, when lev(v)=lev(u)−1 and the second term uses τ_{lev(v)}, the subsequent replacement by τ_{lev(u)} is valid up to a factor 1.1. This should be stated explicitly for completeness, since the displayed chain currently jumps over this detail.
  4. [Appendix A, Proposition 1.2] The doubling-dimension argument is given in detail only for balls centered at the origin. The proof should briefly mention that balls centered at other points are handled by the same exponentially separated scale structure, so the doubling constant is bounded for all centers.

Circularity Check

0 steps flagged

No circularity: the MST approximation is derived from net-hierarchy packing/covering properties and proven auxiliary lemmas, not from fitted parameters or self-citations.

full rationale

The paper's derivation is self-contained. The central algorithm constructs a net hierarchy (Lemma 2.8) and a well-separated pair cover (Lemma 2.11), both proven in the appendices from the packing and covering properties of nets. The WSPC-to-MST lemma (Lemma 2.10) is likewise proven in Appendix B.2 for general metrics and WSPC, extending rather than importing the Euclidean WSPD result. Lemma 3.2, credited to CEF+05, is given a full proof directly in Section 3.2, so the citation is not load-bearing. The error analysis charges approximation error to the MST optimum using lower bounds from net packing, with no fitted parameters and no 'prediction' that reduces to the value of a fitted quantity. The choice of the level ℓ* is computed from net sizes and used only to organize the charging argument; it is not used to embed the target MST weight into the algorithm's input. The proof gaps noted by the reviewer are constant-factor bookkeeping omissions and a level-0 covering detail in the WSPC proof; these are correctness repairs, not circular reductions. No self-citation chain forces the main result, and no ansatz is smuggled in through prior work: the net hierarchy is explicitly defined and constructed rather than assumed as a black box.

Axiom & Free-Parameter Ledger

2 free parameters · 4 axioms · 0 invented entities

The algorithm introduces no new physical or mathematical entities. It relies on standard metric-space axioms and the assumed computational model. The free parameters listed are universal constants in the algorithm's design, not fitted to data.

free parameters (2)
  • level-band width 10 log(1/ε)
    Hand-chosen constant separating low/middle/high level pairs in Algorithm 1; large enough to make the geometric error sums converge to O(ε). Not derived from data.
  • high-level threshold base 1.1
    Chosen so τ_ℓ = 1.1^{ℓ-ℓ*} makes both the error sum Σ 1.1^{-j} and the time sum Σ (1.21/√2)^j converge; works with base-2 logs in the stated form, and the constants are not data-dependent.
axioms (4)
  • standard math Packing property (Lemma 2.3): a ρ-packing set in a doubling metric has size (diam/ρ)^{O(ddim)}
    Used throughout to bound sizes of nets and neighborhoods, e.g., |{u∈N_ℓ: d(x,u)≤2^{ℓ+4}}| ≤ 2^{O(ddim)}.
  • domain assumption Distance-oracle / real-RAM model with constant-time distance queries and arithmetic
    Assumed in Section 1 and used in all running-time bounds; without it, distances cannot be queried in O(1).
  • domain assumption The metric has finite doubling dimension ddim and, after preprocessing, min distance 1 and diameter Δ ≤ n^{10}/ε (aspect-ratio reduction Lemma B.2)
    Theorem 1.1 runs on the reduced set X'; the reconstruction step (B.2) assumes MST(X) ≥ diameter, which holds for any metric.
  • domain assumption Nets can be constructed greedily in near-linear time with the stated packing/covering parameters (Lemma 2.8)
    The proof in Appendix B.1 constructs them; it relies on the packing property and the distance oracle.

pith-pipeline@v1.3.0-alltime-deepseek · 47 in / 47590 out tokens · 1004343 ms · 2026-08-02T05:51:27.486746+00:00 · methodology

0 comments
read the original abstract

The minimum spanning tree (MST) problem is one of the most basic optimization problems on metric spaces and graphs. We study the problem of computing a $(1+\epsilon)$-approximation to the MST of an $n$-point metric space $(X, \mathbf{d})$ of doubling dimension $\mathrm{ddim}$. In doubling metrics, previous deterministic algorithms incur a running time with dependence $\epsilon^{-O(\mathrm{ddim})}$. We give a deterministic algorithm that computes a $(1+\epsilon)$-approximation to MST in time $2^{O(\mathrm{ddim})} n \bigl(\log n + \epsilon^{-1} \log^4(1/\epsilon)\bigr)$. For bounded doubling dimension, this improves the previous dependence on $\epsilon$ from $\epsilon^{-O(\mathrm{ddim})}$ to essentially linear in $\epsilon^{-1}$. Moreover, as a special case, our result improves the previous best deterministic running time for bounded-dimensional Euclidean metrics due to Arya and Mount~[SODA'16] by almost a factor of $\epsilon^{-1}$. We also show that, unlike in bounded-dimensional Euclidean spaces, MSTs in bounded doubling metrics can have arbitrarily large maximum degree, while every doubling metric nevertheless admits a $(1+\epsilon)$-approximate MST of maximum degree $2^{O(\mathrm{ddim})}\log(1/\epsilon)$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 6 canonical work pages

  1. [1]

    Sunil Arya and Timothy M. Chan. Better -dependencies for offline approximate nearest neighbor search, euclidean minimum spanning trees, and -kernels. In Siu - Wing Cheng and Olivier Devillers, editors, 30th Annual Symposium on Computational Geometry, SoCG'14, Kyoto, Japan, June 08 - 11, 2014 , page 416. ACM , 2014. https://doi.org/10.1145/2582112.2582161 ...

    arXiv 2014

  2. [2]

    Agarwal, Herbert Edelsbrunner, and Otfried Schwarzkopf

    Pankaj K. Agarwal, Herbert Edelsbrunner, and Otfried Schwarzkopf. Euclidean minimum spanning trees and bichromatic closest pairs. Discret. Comput. Geom. , 6:407--422, 1991. https://doi.org/10.1007/BF02574698 doi:10.1007/BF02574698

    doi:10.1007/bf02574698 1991

  3. [3]

    Sunil Arya and David M. Mount. A fast and simple algorithm for computing approximate euclidean minimum spanning trees. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 , pages 1220--1233. SIAM , 2016. https://doi.org/10.1137/1.9781611974331.CH85 doi:10.1137/1.97816119...

    work page doi:10.1137/1.9781611974331.ch85 2016

  4. [4]

    Approximating the weight of the euclidean minimum spanning tree in sublinear time

    Artur Czumaj, Funda Erg \" u n, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, and Christian Sohler. Approximating the weight of the euclidean minimum spanning tree in sublinear time. SIAM J. Comput. , 35(1):91--109, 2005. https://doi.org/10.1137/S0097539703435297 doi:10.1137/S0097539703435297

    work page doi:10.1137/s0097539703435297 2005

  5. [5]

    Callahan and S

    Paul B. Callahan and S. Rao Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Vijaya Ramachandran, editor, Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA , pages 291--300. ACM/SIAM , 1993. URL: http://dl.acm.org/citation.cfm?id=313559.313777

    arXiv 1993

  6. [6]

    Callahan and S

    Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM , 42(1):67--90, 1995. https://doi.org/10.1145/200836.200853 doi:10.1145/200836.200853

    arXiv 1995

  7. [7]

    Approximating the minimum spanning tree weight in sublinear time

    Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput. , 34(6):1370--1379, 2005. https://doi.org/10.1137/S0097539702403244 doi:10.1137/S0097539702403244

    work page doi:10.1137/s0097539702403244 2005

  8. [8]

    Estimating the weight of metric minimum spanning trees in sublinear time

    Artur Czumaj and Christian Sohler. Estimating the weight of metric minimum spanning trees in sublinear time. SIAM J. Comput. , 39(3):904--922, 2009. https://doi.org/10.1137/060672121 doi:10.1137/060672121

    work page doi:10.1137/060672121 2009

  9. [9]

    Chan and Da Wei Zheng

    Timothy M. Chan and Da Wei Zheng. Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees. ACM Trans. Algorithms , 20(3):24, 2024. https://doi.org/10.1145/3591357 doi:10.1145/3591357

    doi:10.1145/3591357 2024

  10. [10]

    Fredman and Robert Endre Tarjan

    Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM , 34(3):596--615, 1987. https://doi.org/10.1145/28869.28874 doi:10.1145/28869.28874

    arXiv 1987

  11. [11]

    Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, October 11-14, 2003, Proceedings , pages 534--543. IEEE Computer Society, 2003. https://doi.org/10.1109/SFCS.2003.1238226 doi:10.1109/SFCS.2003.1238226

    Pith/arXiv arXiv 2003

  12. [12]

    Euclidean spanners in high dimensions

    Sariel Har - Peled, Piotr Indyk, and Anastasios Sidiropoulos. Euclidean spanners in high dimensions. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013 , pages 804--809. SIAM , 2013. https://doi.org/10.1137/1.9781611973105.57 doi:10.1137/1....

    doi:10.1137/1.9781611973105.57 2013

  13. [13]

    Fast construction of nets in low-dimensional metrics and their applications

    Sariel Har - Peled and Manor Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. , 35(5):1148--1184, 2006. https://doi.org/10.1137/S0097539704446281 doi:10.1137/S0097539704446281

    doi:10.1137/s0097539704446281 2006

  14. [14]

    Robert Krauthgamer and James R. Lee. Navigating nets: simple algorithms for proximity search. In SODA , pages 798--807. SIAM , 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982913

    arXiv 2004

  15. [15]

    Sublinear-time algorithm for mst-weight revisited

    Gryphon Patlin and Jan van den Brand. Sublinear-time algorithm for mst-weight revisited. In Ioana Oriana Bercea and Rasmus Pagh, editors, 2025 Symposium on Simplicity in Algorithms, SOSA 2025, New Orleans, LA, USA, January 13-15, 2025 , pages 46--53. SIAM , 2025. https://doi.org/10.1137/1.9781611978315.3 doi:10.1137/1.9781611978315.3

    work page doi:10.1137/1.9781611978315.3 2025

  16. [16]

    Closest-point problems

    Michael Ian Shamos and Dan Hoey. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975 , pages 151--162. IEEE Computer Society, 1975. https://doi.org/10.1109/SFCS.1975.8 doi:10.1109/SFCS.1975.8

    doi:10.1109/sfcs.1975.8 1975

  17. [17]

    Bypassing the embedding: algorithms for low dimensional metrics

    Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In L \' a szl \' o Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004 , pages 281--290. ACM , 2004. https://doi.org/10.1145/1007352.1007399 doi:10.1145/1007352.1007399

    arXiv 2004

  18. [18]

    Pravin M. Vaidya. A sparse graph almost as good as the complete graph on points in K dimensions. Discret. Comput. Geom. , 6:369--381, 1991. https://doi.org/10.1007/BF02574695 doi:10.1007/BF02574695

    work page doi:10.1007/bf02574695 1991

  19. [19]

    On constructing minimum spanning trees in k-dimensional spaces and related problems

    Andrew Chi - Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. , 11(4):721--736, 1982. https://doi.org/10.1137/0211059 doi:10.1137/0211059

    doi:10.1137/0211059 1982