{"id":"f9ca45e1-4ca1-40b3-9c8d-309b52f3c70d","arxiv_id":"2509.01443","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Near-optimal dynamic Steiner spanners are constructed in all three constant-curvature geometries via a quadtree approach, and the hyperbolic-plane 2-spanner problem is settled at Θ(n log n) edges.","lead":"Steiner spanners, sparse graphs that approximate all pairwise distances, are built with near-optimal edge counts in Euclidean, spherical, and hyperbolic spaces, and maintained under point insertions and deletions. The paper also proves the hyperbolic plane requires and admits Θ(n log n) edges for 2-spanners.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.4's detour bound is off by a factor of 2 and its triangle-inequality case has a gap; constants may absorb it, but the lemma as stated is unsupported.","rationale":"The reader's weakest assumption is the same Lemma 4.4 overclaim. I verified the arithmetic: the proof's two halves each give +δ², so the sum has +2δ². The applications use the slack as ε diam(C) rather than 2ε diam(C); because all uses have diam(C) ≤ |pq| up to constants, the asymptotic edge and stretch bounds are unaffected and the central theorem can be recovered by adjusting ε by a constant factor. The additional δ≥√2 gap is in the same lemma and should be fixed in the same pass. This is a genuine proof gap but not a threat to the main asymptotic claim, so the CONDITIONAL verdict stands unchanged.","tokens_in":36368,"tokens_out":33348,"duration_ms":345871,"concrete_test":"Recompute Lemma 4.4 in a concrete configuration: p=(0,1), q=(L,1) with L=4·sinh(1) (so H at x=L/2 has distance ≥2 from p,q), x=(L/2,e^1.5), and compare |px|+|xq| with |pq|+2.25 and |pq|+3. Then re-derive Lemma 4.5 with the corrected +2δ² bound and verify the final stretch is (1+O(ε)) for all admissible δ, especially δ∈[√2,2). If the slack exceeds ε|pq| for some δ, the hyperbolic construction in Lemma 4.5/Theorem 4.13 fails; if not, only the lemma statement needs amendment.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Lemma 4.4 only yields |px| ≤ |py|+δ² and |xq| ≤ |qy|+δ², hence |px|+|xq| ≤ |pq|+2δ², not the stated |pq|+δ². Lemma 4.5 and Theorem 4.13 invoke the lemma with δ² = ε diam(C) to get a slack of ε diam(C) and conclude a (1+ε)-stretch; the correct slack 2ε diam(C) is still O(ε) when diam(C) ≤ |pq|, so the asymptotic results survive after redefining ε by a constant. The gap is therefore not fatal to Theorem 1.1, but the lemma statement overclaims and the proof must be corrected. In addition, the proof's 'if δ ≥ √2 then the triangle inequality suffices' is only valid for δ ≥ 2; the interval [√2, 2) is left unhandled, and since applications can have δ in that range, this needs a separate argument. Because Lemma 4.4 is the only bridge for the medium-distance hyperbolic regime (|pq| between 1 and 1/ε), the repair must be explicit.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents dynamic Steiner (1+ε)-spanners of size O_d(ε^{(1-d)/2} log(1/ε) n) in Euclidean, spherical, and hyperbolic d-dimensional space, with update time O_d(ε^{(1-d)/2} log(1/ε) log n). The Euclidean result matches recent work of Chang et al. and the spherical/hyperbolic results are new. The paper also proves an Ω(n log n) lower bound for 2-spanners in the hyperbolic plane and gives an O_d(n log n) 2-spanner in H^d, an ε-additive hyperbolic Steiner spanner with near-linear size (up to inverse-Ackermann factor), extensions to constant-curvature surfaces and quotients, and dynamic approximate nearest-neighbour and bichromatic closest-pair data structures. The constructions are quadtree-based and are substantially simpler than previous WSPD/LSO-based approaches.","tokens_in":36697,"tokens_out":21978,"duration_ms":249673,"significance":"If the technical gaps are repaired, this is a significant contribution. It nearly settles the optimal size of Steiner (1+ε)-spanners in the three constant-curvature geometries, and it is the first near-optimal result in the non-doubling hyperbolic setting. The quadtree framework is elegant, yields dynamic maintenance almost for free, and gives the first dynamic ANN/BCP structures specific to spherical and hyperbolic spaces. The lower bound for 2-spanners in H^2 and the matching upper bound for all d resolve a question left open by previous work. The paper builds on the authors' own published hyperbolic quadtree [KvW24] as an independent foundation; I see no circularity or parameter fitting. The strengths are the simplicity of the main constructions and the breadth of consequences (tree covers, quotient spaces, additive spanners).","major_comments":[{"comment":"The lemma statement claims |px|+|xq| ≤ |pq|+δ², but the proof derives only |px| ≤ δ²+|py| and |xq| ≤ δ²+|qy|, which sum to |pq|+2δ². The opening argument 'if δ≥√2 then the lemma already holds by the triangle inequality' is also only valid for δ≥2; the interval [√2,2) is left unhandled. The applications in Lemma 4.5 and Theorem 4.13 invoke the lemma with δ²≈ε diam(C), and replacing the claimed slack by 2ε diam(C) still yields the asymptotic (1+O(ε))-stretch after reparameterizing ε by a constant, so the main theorem is likely salvageable. Nevertheless, Lemma 4.4 is load-bearing for the medium-distance hyperbolic regime, and the statement and proof must be corrected or explicitly weakened.","section":"§4.1, Lemma 4.4"},{"comment":"Lemma 4.5 applies Lemma 4.4 to a Steiner point s∈cov(C′), where cov(C′) covers the horosphere slice C′|{1/6}. Lemma 4.4 is stated for a hyperplane H separating p and q. A horizontal slice of a quadtree cell in the half-space model is a horosphere, not a hyperbolic hyperplane, and the application does not justify that p′,q′ are separated by such a hyperplane. The proof of Lemma 4.4 in fact appears to use only dist(p,x),dist(q,x)≥2, not that H is a hyperplane. The statement and the application should be aligned, either by generalizing Lemma 4.4 to any set S with x∈S and dist(p,S),dist(q,S)≥2, or by showing that the relevant slice can be replaced by a genuine separating hyperplane.","section":"§4.1, Lemma 4.5"},{"comment":"The transition from the centered pair p_{−k},p_k to the blocks A,B,C is not justified. The bound |α|<16 was derived for the middle vertex of a two-hop path between p_{−k} and p_k; in the block argument, v is not necessarily the index-halfway point b between a and c, and no generalized inequality is proved that would imply 'the index distance between b and v must be less than 48k.' Additionally, 'its index distance to a is at most 3k' is false for arbitrary choices a∈A,c∈C (the midpoint can be about 3.5k away from a). Since this counting argument is the source of the Ω(n log n) lower bound and of the claimed optimality of the bipartite construction, the proof needs to be rewritten with a precise specification of the 2k disjoint pairs and a generalized version of the centered-pair bound.","section":"§4.1.1, Lemma 4.9"}],"minor_comments":[{"comment":"The line 'min{|py|,|qy|} ≥ 1/6|py|' appears to be a typo; it should be '≥ |pq|/6' (or similar).","section":"§3.2, Theorem 3.7"},{"comment":"The hyperbolic proof establishes |px| ≤ (1 + e^Δ ε/(2Δ))|py|, which is stronger than the stated (1+e^Δ ε)|py|. The constants should be stated consistently.","section":"§3.2, Lemma 3.4"},{"comment":"The proof concludes with 'this is a Steiner (1+ε′)-spanner for ε′=2ε.' The theorem statement should name the final parameter consistently, e.g., by stating the construction with a parameter ε0 and concluding stretch 1+ε0/2.","section":"§4.2, Theorem 4.13"},{"comment":"The phrase 'maintain an (1+ε)-approximate' should be 'maintain a (1+ε)-approximate'.","section":"§5.2, Theorem 5.5"}],"recommendation":"major_revision","confidential_remarks":"The gaps in Lemma 4.4 and Lemma 4.9 are local and appear repairable within the scope of the manuscript. The central construction is elegant and the asymptotic claims are likely correct with constant-factor adjustments. The manuscript is a strong fit for a serious computational geometry journal; I see no issues of novelty or attribution. The main risk is that the hyperbolic medium-distance bridge (Lemma 4.4 and its application to horosphere slices) needs a fully correct statement before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main thing you should know: this is a substantial paper. It gets the near-optimal size bound Od(ε^{1−d)/2} log(1/ε) n) for Steiner spanners in Euclidean, spherical, and hyperbolic space, and it does it with a quadtree construction that is genuinely different from the Chang et al. Euclidean result. The dynamic maintenance is a real bonus, and the 2-spanner lower bound in the hyperbolic plane plus the matching upper bound settle a question that was open.\n\nWhat is actually new and good: the quadtree approach itself, the spherical and hyperbolic generalizations, the dynamic spanner data structures, and the improved 2-spanner results. The paper is honest about the dependence on the authors' earlier hyperbolic quadtree, and that prior work is published and independently citable. I see no sign of parameter fitting or circularity.\n\nThe soft spots are real but not fatal. Lemma 4.4 is the key detour bound for the medium-distance hyperbolic regime, and its proof overclaims. The triangle inequality argument only works when δ ≥ 2, not δ ≥ √2 as written, so the interval [√2, 2) is unhandled. Also, the hyperbolic Pythagorean step gives |px| ≤ |py| + δ² and |xq| ≤ |qy| + δ², which sums to |pq| + 2δ², not the stated |pq| + δ². That factor of 2 gets absorbed by the slack in Lemma 4.5 and Theorem 4.13, so the asymptotic theorems survive, but the lemma as stated is not proven. This needs an explicit repair before I would call the paper fully correct.\n\nI disagree with one of the reader's concerns: Lemma 4.9's assumption that the middle of the 2-hop path is an input point is fine, because the lemma is about standard (non-Steiner) spanners, and the transformation in Theorem 4.8 reduces bipartite Steiner spanners exactly to that setting. The lower bound argument itself looks OK to me, modulo the usual hyperbolic trig checks, which I did not do line by line.\n\nWho is this for? Anyone working on spanners, hyperbolic geometry, or dynamic geometric data structures. It deserves a serious referee: the main theorems are important and likely correct, but they need a clean fix of Lemma 4.4 before publication. I would send it to a strong venue and ask for a revision, not a rewrite.","headline":"Strong paper that nearly settles the Steiner spanner trade-off in all three constant-curvature spaces, with a real but fixable gap in the hyperbolic detour lemma.","tokens_in":37135,"tokens_out":4175,"would_cite":true,"duration_ms":51775,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68U05","05C85"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single quadtree construction matches the near-optimal spanner bound in Euclidean, spherical and hyperbolic space.","keywords":["Steiner spanners","hyperbolic geometry","spherical geometry","quadtrees","dynamic spanners","approximate nearest neighbours","constant curvature","bichromatic closest pair"],"falsifier":"Evaluate |px|+|xq|−|pq| numerically in the hyperbolic plane for p and q with |py|=|qy|=2 and a point x at distance δ=1 from the segment pq on a hyperplane at distance at least 2 from both p and q; if the excess exceeds 1, Lemma 4.4's stated bound fails exactly as written. A broader check would implement the d=2 and d=3 hyperbolic constructions on point sets with mutual distances in [1, 1/ε] and measure the total edge count, testing whether the ε^{(1-d)/2} scaling holds or degrades to ε^{-1} in the plane.","tokens_in":36319,"feed_emoji":"📐","tokens_out":5742,"duration_ms":66755,"temperature":0.7,"pith_summary":"This paper claims that Steiner spanners with nearly optimal edge counts are possible not just in Euclidean space but also in spherical and hyperbolic space. For any n-point set in d-dimensional Euclidean, spherical or hyperbolic space, it constructs a Steiner (1+ε)-spanner with O_d(ε^{(1-d)/2} log(1/ε) n) edges, which nearly matches the known lower bound, and maintains it dynamically in O_d(ε^{(1-d)/2} log(1/ε) log n) time per update. The hyperbolic case is the main obstacle: the space is not doubling, so Euclidean techniques do not transfer directly, and the paper bridges the gap between small and large scales with new detour estimates. A reader should care because this nearly settles the size-versus-stretch question for the three constant-curvature geometries, and the dynamic structure gives improved data structures for approximate nearest neighbours and bichromatic closest pair in all three spaces.","feed_headline":"Quadtrees match near-optimal spanner size in three geometries","feed_subtitle":"Same edge bound in Euclidean, spherical and hyperbolic space, with log-time updates and a matching 2-spanner.","key_machinery":"The arguments run on quadtrees: standard Euclidean quadtrees, spherical quadtrees built from two stereographic projections, and the hyperbolic quadtree of [KvW24], whose cells are isometric cube-based horoboxes and whose large-scale structure is tree-like. The key geometric estimate is Lemma 3.4, which bounds the detour through a point x near segment pq by (1+ε)|pq| when x lies within distance √ε min(|py|,|qy|) of pq, and in the hyperbolic large-scale regime this role is played by Lemma 4.4, which claims |px|+|xq| ≤ |pq|+δ² for a point x on a separating hyperplane at distance δ from pq. At very large scales Lemma 4.11 converts the exponential divergence of hyperbolic geodesics into an embedd","core_discovery":"The central claim is Theorem 1.1: for ε∈(0,1/2] and any n-point set P in Euclidean, spherical or hyperbolic d-space, there is a Steiner (1+ε)-spanner with O_d(ε^{(1-d)/2} log(1/ε) n) edges, maintainable dynamically in O_d(ε^{(1-d)/2} log(1/ε) log n) time per insertion or deletion. This nearly matches the Ω(ε^{(1-d)/2} n) lower bound of Bhore and Tóth, which the paper notes transfers to the other geometries because both spaces are locally Euclidean. The construction improves the previous hyperbolic edge count from ε^{-d} log(1/ε)n to ε^{(1-d)/2} log(1/ε)n. As a by-product, the paper proves that 2-spanners in the hyperbolic plane require Ω(n log n) edges, constructs 2-spanners with O_d(n log n","pith_inferences":["The ε^{(1-d)/2} exponent in the edge count appears to be governed by local Euclidean dimension rather than the space's global growth, so a similar exponent might hold for other locally Euclidean manifolds with a quadtree-like decomposition.","The bipartite lower bound in the hyperbolic plane suggests a structural obstruction: without Steiner-to-Steiner edges, the tree-like horizon forces Ω(n/ε) edges, and removing bipartiteness is exactly what unlocks the ε^{-1/2} scaling in H².","The order-based update mechanism could be adapted to other quadtree-decomposable spaces beyond constant curvature, since the update time tracks the degree of a point in the spanner, which is a local quantity.","A concrete testable extension: use the medium-distance detour estimate to prune quadtree cells and speed up local spanner maintenance, possibly reducing the log(1/ε) factor or improving constant-fraction dependence on dimension.","The additive hyperbolic spanner's dependence on the inverse Ackermann function hints that a threshold near linear size may require a genuinely new hop-compression technique beyond transitive-closure spanners."],"forward_implications":["Dynamic (1+ε)-approximate nearest neighbour and bichromatic closest pair data structures in S^d, E^d and H^d with O_d(ε^{(1-d)/2} log(1/ε) log n) update time follow directly from the maintained spanner.","A 2-spanner with O_d(n log n) edges exists in all dimensions, matching the new Ω(n log n) lower bound in the hyperbolic plane and settling the question of whether subquadratic 2-spanners can achieve linear size there.","An ε-additive Steiner spanner exists in hyperbolic space with O_d(ε^{(1-d)/2} log(α(n)/ε) n) edges, in contrast to Euclidean space where subquadratic additive Steiner spanners are impossible.","The same Steiner spanners give tree covers of size O_d(ε^{(1-d)/2} log(1/ε) n), generalising the Euclidean tree-cover result.","The constructions extend with a g^{O(g)} factor to closed orientable constant-curvature surfaces of genus g, covering spheres, tori and hyperbolic surfaces.","The strengthened hyperbolic Steiner spanner improves the previous ε^{-d} scaling to ε^{(1-d)/2}, which is the optimal exponent up to the log(1/ε) factor in all three constant-curvature geometries."],"supporting_citations":[{"why":"Supplies the hyperbolic quadtree and its L-order properties, the base construction that the paper improves from ε^{-d} to ε^{(1-d)/2} edges.","marker":"[KvW24]"},{"why":"Gives the Euclidean Steiner spanner lower bound Ω(ε^{(1-d)/2} n) that the main theorem nearly matches and ports to S^d and H^d.","marker":"[BT22]"},{"why":"Provides the earlier Euclidean Steiner spanner with O_d(ε^{(1-d)/2} log(1/ε) n) edges, the edge count that the paper reproduces with a different, dynamic method.","marker":"[CCL+24]"},{"why":"Supplies the locality-sensitive orderings and shifted-quadtree lemma used for finding small cells and for dynamic order maintenance.","marker":"[CHPJ20]"},{"why":"Contains the Euclidean detour lemma that Lemma 3.4 generalises to spherical and hyperbolic geometry.","marker":"[LS22]"},{"why":"Establishes the earlier Euclidean-style Steiner spanner in Gromov-hyperbolic spaces, the result whose edge count is improved here.","marker":"[KL06]"},{"why":"Gives an additive-error Steiner spanner in H^d and the transitive-closure idea that the ε-additive construction extends.","marker":"[PV25]"},{"why":"Provides the transitive-closure spanner on rooted trees used to collapse hop counts in the additive hyperbolic construction.","marker":"[Tho97]"},{"why":"Supplies the boundary-crossing bound for Dirichlet domains that enables the extension to hyperbolic surfaces of genus g.","marker":"[DKT24]"},{"why":"Provides the shift-based cell-containment result used to construct the spherical quadtrees with the required diameter property.","marker":"[Cha98]"}],"fun_headline_variants":["Quadtrees give near-optimal dynamic spanners in curved spaces","Same near-optimal spanner size in Euclidean, spherical, hyperbolic","Optimal-up-to-log spanners via quadtrees in three geometries","Dynamic Steiner spanners match lower bounds in constant curvature","Quadtree spanners: near-optimal edges in Euclidean and curved spaces"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"Lemma 4.4, stated as the detour bound |px|+|xq| ≤ |pq|+δ², is proved only with an extra factor 2: the proof establishes |px| ≤ |py|+δ² and |xq| ≤ |qy|+δ², which sum to |pq|+2δ²; this estimate is the load-bearing bound for medium hyperbolic distances, and the asymptotic edge count survives only because the slack is absorbed by constants in later lemmas.","fun_headline_variants_meta":{"raw":{"variants":["Quadtrees give near-optimal dynamic spanners in curved spaces","Same near-optimal spanner size in Euclidean, spherical, hyperbolic","Optimal-up-to-log spanners via quadtrees in three geometries","Dynamic Steiner spanners match lower bounds in constant curvature","Quadtree spanners: near-optimal edges in Euclidean and curved spaces"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000215,"raw_usage":{"total_tokens":1360,"prompt_tokens":932,"completion_tokens":428,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":676,"completion_tokens_details":{"reasoning_tokens":337}},"tokens_in":676,"tokens_out":428,"duration_ms":5149,"temperature":1.0,"reasoning_tokens":337,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T12:33:50.423751+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate |px|+|xq|−|pq| numerically in the hyperbolic plane for p and q with |py|=|qy|=2 and a point x at distance δ=1 from the segment pq on a hyperplane at distance at least 2 from both p and q; if the excess exceeds 1, Lemma 4.4's stated bound fails exactly as written. A broader check would implement the d=2 and d=3 hyperbolic constructions on point sets with mutual distances in [1, 1/ε] and measure the total edge count, testing whether the ε^{(1-d)/2} scaling holds or degrades to ε^{-1} in the plane.","supporting_citations":[],"review_version":1}