Pith. sign in

REVIEW 3 major objections 4 minor 61 references

Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

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

Pith's one-line read A single quadtree construction matches the near-optimal spanner bound in Euclidean, spherical and hyperbolic space.

desk verdict 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. read the letter →

arxiv 2509.01443 v1 pith:T5JJGX6O submitted 2025-09-01 cs.CG

Sándor Kisfaludi-Bak , Geert van Wordragen This is my paper · ORCID
classification cs.CG MSC 68U0505C85
keywords Steinerspannershyperbolicgeometrysphericalquadtreesdynamicapproximatenearestneighboursconstantcurvaturebichromaticclosestpair
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 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.

What carries the argument

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

What would settle it

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.

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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

Reading between the lines

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

  • 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.
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 / 4 minor

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.

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 (3)
  1. [§4.1, Lemma 4.4] 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.
  2. [§4.1, Lemma 4.5] 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.
  3. [§4.1.1, Lemma 4.9] 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.
minor comments (4)
  1. [§3.2, Theorem 3.7] The line 'min{|py|,|qy|} ≥ 1/6|py|' appears to be a typo; it should be '≥ |pq|/6' (or similar).
  2. [§3.2, Lemma 3.4] The hyperbolic proof establishes |px| ≤ (1 + e^Δ ε/(2Δ))|py|, which is stronger than the stated (1+e^Δ ε)|py|. The constants should be stated consistently.
  3. [§4.2, Theorem 4.13] 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.
  4. [§5.2, Theorem 5.5] The phrase 'maintain an (1+ε)-approximate' should be 'maintain a (1+ε)-approximate'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central derivation is self-contained and relies on independent published foundations, not on its own target claim.

full rationale

The paper's main theorem is not defined in terms of its conclusion. The edge bounds follow by counting Steiner cover points on small-boundary quadtree cells and the stretch follows from geometric detour lemmas (Lemma 3.4, Lemma 4.4, Lemma 4.11), not by assuming the target spanner property. Where the paper cites its own prior work, namely the hyperbolic quadtree of [KvW24] (Lemma 2.1) and its shifting lemma (Lemma 4.2), these are published, independently stated results with their own proofs, not a uniqueness theorem or a fitted parameter; they are legitimate foundations. The lower-bound comparison uses Bhore and Tóth [BT22], external to this paper. No parameter is fitted to a subset of data and then renamed a prediction, and no equation is shown to be equal to its input by construction. The skeptical concern about Lemma 4.4 — that the proof only yields |px|+|xq| ≤ |pq|+2δ² and that the δ ≥ √2 case has a gap for [√2,2) — is a correctness/constant issue, not a circularity: the asymptotic constants absorb the missing factor and the central claim does not reduce to Lemma 4.4 by definition. Therefore the circularity score is 0.

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

No free parameters are fitted to data; all constants are universal. The paper inherits the hyperbolic quadtree from prior work and relies on standard external results; no new entities (particles, forces, dimensions) are postulated. The only new constructions are algorithmic (spherical quadtree, Steiner point placements), not invented physical or mathematical entities.

assumptions (6)
  • standard math Standard Euclidean quadtree properties: shifted quadtrees provide a cell of diameter O(d√d)|pq| containing any pair; bounded growth and small-boundary cells.
    Inherited from [CHPJ20] Lemma 3.1 and [HP11]; used throughout Section 3 for the Euclidean, spherical, and small-scale hyperbolic constructions.
  • domain assumption The hyperbolic quadtree of [KvW24] satisfies Lemma 2.1 (i)-(v).
    The paper relies on the existence and properties of the hyperbolic quadtree with O(d) shifts, cell diameter Θ(2^ℓ), bounded children, and L-order queries; this is prior published work by the same authors.
  • standard math Bhore-Tóth lower bound Ω(ε^{(1-d)/2} n) for Euclidean Steiner spanners.
    Used to argue optimality in all three geometries via local-Euclidean embeddings of the hard instance.
  • standard math Thorup's O(α(n)) transitive closure spanner on trees.
    Used in Theorem 1.3 to bound hop count; external result [Tho97].
  • standard math Killing-Hopf theorem and Dirichlet domain properties for constant-curvature surfaces.
    Used in Section 5.1 for closed orientable surfaces; relies on [DKT24] Lemma 5.
  • domain assumption Existence of an upper bound Δ on pairwise distances; the algorithms require a finite Δ but the bounds are independent of it.
    Mentioned in Section 3.1; practical input coordinates provide such a bound, and it does not affect any asymptotic result.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces." pith.science (2026). https://pith.science/paper/T5JJGX6O

@misc{pith2026250901443,
  author       = {Pith},
  title        = {Pith review of: Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T5JJGX6O}},
  note         = {Machine review of arXiv:2509.01443}
}
abstract

We consider Steiner spanners in Euclidean and non-Euclidean geometries. In the Euclidean setting, a recent line of work initiated by Le and Solomon [FOCS'19] and further improved by Chang et al. [SoCG'24] obtained Steiner $(1+\varepsilon)$-spanners of size $O_d(\varepsilon^{(1-d)/2}\log(1/\varepsilon)n)$, nearly matching the lower bounds of Bhore and T\'oth [SIDMA'22]. We obtain Steiner $(1+\varepsilon)$-spanners of size $O_d(\varepsilon^{(1-d)/2}\log(1/\varepsilon)n)$ not only in $d$-dimensional Euclidean space, but also in $d$-dimensional spherical and hyperbolic space. For any fixed dimension $d$, the obtained edge count is optimal up to an $O(\log(1/\varepsilon))$ factor in each of these spaces. Unlike earlier constructions, our Steiner spanners are based on simple quadtrees, and they can be dynamically maintained, leading to efficient data structures for dynamic approximate nearest neighbours and bichromatic closest pair. In the hyperbolic setting, we also show that $2$-spanners in the hyperbolic plane must have $\Omega(n\log n)$ edges, and we obtain a $2$-spanner of size $O_d(n\log n)$ in $d$-dimensional hyperbolic space, matching our lower bound for any constant $d$. Finally, we give a Steiner spanner with additive error $\varepsilon$ in hyperbolic space with $O_d(\varepsilon^{(1-d)/2}\log(\alpha(n)/\varepsilon)n)$ edges, where $\alpha(n)$ is the inverse Ackermann function. Our techniques generalize to closed orientable surfaces of constant curvature as well as to some quotient spaces.

Figures

Figures reproduced from arXiv: 2509.01443 by the authors.

Figure 1
Figure 1. A patch of the binary tiling shown in the half-plane model. Note that all tiles are isometric. [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A Euclidean quadtree and the hyperbolic quadtree of [ [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. The Steiner spanner in E 2 and the bipartite Steiner spanner in H2 . to a Steiner point that is chosen from a grid-like point set on a cell boundary separating p ′ and q ′ . This Steiner spanner proves Theorem 1.1 for S d , E d and small-diameter point sets in Hd . By construction this is a bipartite Steiner spanner (i.e. every edge is between an input point and a Steiner point). This makes it easy to turn it into a… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Grid on S 2 . In the hyperbolic case, we use the quadtree of [KvW24] described in Section 2. For spherical geometry we define a new quadtree. For that, first fix an arbitrary pair of antipodal points o +, o− and consider the stereographic projection πstereo from o − on…
Figure 5
Figure 5. Figure 5: The tree T 0 (P) for the black points P. This leaves the question of whether a 2-spanner with Od(n log n) edges is possible, and in fact, it is. Let us first introduce some concepts that will also play a key role in Section 4.2. Given points P ⊂ Hd , we define the tree…
Figure 6
Figure 6. Figure 6: The 2-spanner uses the path p, s′ , q instead of the Steiner path p, s, q. Since s is within distance 1/4 to the line pq and |s ′ s| ≤ min{|sp|, |sq|}, we can show that |ps′ | + |s ′ q| ≤ 2|pq|. Proof. We do the construction for every shift i given by Lemma 4.3 and the…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 34 canonical work pages

  1. [1]

    Dobkin, Deborah Joseph, and Jos \' e Soares

    Ingo Alth \" o fer, Gautam Das, David P. Dobkin, Deborah Joseph, and Jos \' e Soares. On sparse spanners of weighted graphs. Discret. Comput. Geom. , 9:81--100, 1993. https://doi.org/10.1007/BF02189308 doi:10.1007/BF02189308

    doi:10.1007/bf02189308 1993

  2. [2]

    Mount, Jeffrey S

    Sunil Arya, Gautam Das, David M. Mount, Jeffrey S. Salowe, and Michiel H. M. Smid. Euclidean spanners: short, thin, and lanky. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA , pages 489--498. ACM , 1995. https://doi.org/10.1145/225058.225191 doi:10.1145/225058.225191

    work page arXiv 1995

  3. [3]

    Hyperbolic D elaunay complexes and V oronoi diagrams made practical

    Mikhail Bogdanov, Olivier Devillers, and Monique Teillaud. Hyperbolic D elaunay complexes and V oronoi diagrams made practical. J. Comput. Geom. , 5(1):56--85, 2014. https://doi.org/10.20382/JOCG.V5I1A4 doi:10.20382/JOCG.V5I1A4

    doi:10.20382/jocg.v5i1a4 2014

  4. [4]

    Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth

    MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and D \' a niel Marx. Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. J. ACM , 58(5):21:1--21:37, 2011. https://doi.org/10.1145/2027216.2027219 doi:10.1145/2027216.2027219

    work page arXiv 2011

  5. [5]

    o m \" o t \

    Sujoy Bhore, Bal \' a zs Keszegh, Andrey Kupavskii, Hung Le, Alexandre Louvet, D \" o m \" o t \" o r P \' a lv \" o lgyi, and Csaba D. T \' o th. Spanners in planar domains via S teiner spanners and non- S teiner tree covers. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025 ...

    work page doi:10.1137/1.9781611978322.145 2025

  6. [6]

    Embedding of hyperbolic spaces in the product of trees

    Sergei Buyalo and Viktor Schroeder. Embedding of hyperbolic spaces in the product of trees. Geom. Dedicata , 113:75--93, 2005. https://doi.org/10.1007/s10711-005-3124-9 doi:10.1007/s10711-005-3124-9

    doi:10.1007/s10711-005-3124-9 2005

  7. [7]

    A product of trees as universal space for hyperbolic groups

    Sergei Buyalo and Viktor Schroeder. A product of trees as universal space for hyperbolic groups, 2005. https://arxiv.org/abs/math/0509355 arXiv:math/0509355

    work page Pith review arXiv 2005

  8. [8]

    T \' o th

    Sujoy Bhore and Csaba D. T \' o th. Euclidean S teiner spanners: Light and sparse. SIAM J. Discret. Math. , 36(3):2411--2444, 2022. https://doi.org/10.1137/22M1502707 doi:10.1137/22M1502707

    doi:10.1137/22m1502707 2022

Show all 61 references
  1. [9]

    Structure and independence in hyperbolic uniform disk graphs

    Thomas Bl \" a sius, Jean - Pierre von der Heydt, S \' a ndor Kisfaludi - Bak, Marcus Wilhelm, and Geert van Wordragen. Structure and independence in hyperbolic uniform disk graphs. In 41st International Symposium on Computational Geometry, SoCG 2025, June 23-27, 2025, Kanazaw...

    2025 doi

  2. [10]

    Covering planar metrics (and beyond): O(1) trees suffice

    Hsien - Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. Covering planar metrics (and beyond): O(1) trees suffice. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages ...

    2023

  3. [11]

    Optimal E uclidean tree covers

    Hsien - Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, and Cuong Than. Optimal E uclidean tree covers. In 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece , volume 293 of LIPIcs , pages 37:1--37:15. Schl...

    2024 doi

  4. [12]

    Tightening curves on surfaces monotonically with applications

    Hsien - Chih Chang and Arnaud de Mesmay. Tightening curves on surfaces monotonically with applications. ACM Trans. Algorithms , 18(4):36:1--36:32, 2022. https://doi.org/10.1145/3558097 doi:10.1145/3558097

    2022 doi

  5. [13]

    T. - H. Hubert Chan and Anupam Gupta. Small hop-diameter sparse spanners for doubling metrics. Discret. Comput. Geom. , 41(1):28--44, 2009. https://doi.org/10.1007/S00454-008-9115-5 doi:10.1007/S00454-008-9115-5

    2009 doi

  6. [14]

    Timothy M. Chan. Approximate nearest neighbor queries revisited. Discrete & Computational Geometry , 20(3):359--373, Oct 1998. https://doi.org/10.1007/PL00009390 doi:10.1007/PL00009390

    1998 doi

  7. [15]

    There is a planar graph almost as good as the complete graph

    P Chew. There is a planar graph almost as good as the complete graph. In Proceedings of the Second Annual Symposium on Computational Geometry , SoCG '86, page 169–177, New York, NY, USA, 1986. Association for Computing Machinery. https://doi.org/10.1145/10515.10534 doi:10.1145...

    1986

  8. [16]

    Chan, Sariel Har-Peled, and Mitchell Jones

    Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones. On locality-sensitive orderings and their applications. SIAM Journal on Computing , 49(3):583--600, 2020. https://doi.org/10.1137/19M1246493 doi:10.1137/19M1246493

    2020 doi

  9. [17]

    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

    1995

  10. [18]

    Clarkson

    K. Clarkson. Approximation algorithms for shortest path motion planning. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing , STOC '87, page 56–65, New York, NY, USA, 1987. Association for Computing Machinery. https://doi.org/10.1145/28395.28402 doi:1...

    1987

  11. [19]

    T. - H. Hubert Chan, Mingfei Li, Li Ning, and Shay Solomon. New doubling spanners: Better and simpler. SIAM J. Comput. , 44(1):37--53, 2015. https://doi.org/10.1137/130930984 doi:10.1137/130930984

    2015 doi

  12. [20]

    Hyperbolic graph convolutional neural networks

    Ines Chami, Zhitao Ying, Christopher R\' e , and Jure Leskovec. Hyperbolic graph convolutional neural networks. In Advances in Neural Information Processing Systems , volume 32. Curran Associates, Inc., 2019. URL: https://proceedings.neurips.cc/paper_files/paper/2019/file/0415...

    2019

  13. [21]

    van Kreveld, and Mark H

    Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational geometry: algorithms and applications, 3rd Edition . Springer, 2008. https://doi.org/10.1007/978-3-540-77974-2 doi:10.1007/978-3-540-77974-2

    2008 doi

  14. [22]

    Dolbilin and Daniel H

    Nikolai P. Dolbilin and Daniel H. Huson. Periodic D elone tilings. Periodica Mathematica Hungarica , 34:57--64, 1997. https://doi.org/10.1023/A:1004272423695 doi:10.1023/A:1004272423695

    1997 doi

  15. [23]

    Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar

    Erik D. Demaine, MohammadTaghi Hajiaghayi, and Bojan Mohar. Approximation algorithms via contraction decomposition. Comb. , 30(5):533--552, 2010. https://doi.org/10.1007/S00493-010-2341-5 doi:10.1007/S00493-010-2341-5

    2010 doi

  16. [24]

    Representing infinite periodic hyperbolic D elaunay triangulations using finitely many D irichlet domains

    Vincent Despr \' e , Benedikt Kolbe, and Monique Teillaud. Representing infinite periodic hyperbolic D elaunay triangulations using finitely many D irichlet domains. Discret. Comput. Geom. , 72(1):1--28, 2024. https://doi.org/10.1007/S00454-024-00653-X doi:10.1007/S00454-024-00653-X

    2024 doi

  17. [25]

    The space of spheres, a geometric tool to unify duality results on Voronoi diagrams

    Olivier Devillers, Stefan Meiser, and Monique Teillaud. The space of spheres, a geometric tool to unify duality results on Voronoi diagrams . In Canadian Conference on Computational Geometry , pages 263--268, 1992. URL: https://inria.hal.science/inria-00074941

    1992

  18. [26]

    A fast algorithm for constructing sparse E uclidean spanners

    Gautam Das and Giri Narasimhan. A fast algorithm for constructing sparse E uclidean spanners. Int. J. Comput. Geom. Appl. , 7(4):297--315, 1997. https://doi.org/10.1142/S0218195997000193 doi:10.1142/S0218195997000193

    1997 doi

  19. [27]

    Untangling graphs on surfaces

    \' E ric Colin de Verdi \` e re, Vincent Despr \' e , and Lo \" c Dubois. Untangling graphs on surfaces. In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 4909--4941. SIAM , 2024. https://doi.org/10...

    2024 doi

  20. [28]

    Tightening nonsimple paths and cycles on surfaces

    \' E ric Colin de Verdi \` e re and Jeff Erickson. Tightening nonsimple paths and cycles on surfaces. SIAM J. Comput. , 39(8):3784--3813, 2010. https://doi.org/10.1137/090761653 doi:10.1137/090761653

    2010 doi

  21. [29]

    Locality-sensitive orderings and applications to reliable spanners

    Arnold Filtser and Hung Le. Locality-sensitive orderings and applications to reliable spanners. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022 , pages 1066--1079. ACM , 2022. https://doi.org/10.1145/3519935.3520042 doi:10....

    2022

  22. [30]

    An effective way to represent quadtrees

    Irene Gargantini. An effective way to represent quadtrees. Commun. ACM , 25(12):905--910, 1982. https://doi.org/10.1145/358728.358741 doi:10.1145/358728.358741

    1982

  23. [31]

    Hyperbolic neural networks

    Octavian - Eugen Ganea, Gary B \' e cigneul, and Thomas Hofmann. Hyperbolic neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr \' e al, Canada , page...

    2018

  24. [32]

    Guibas, and An Thai Nguyen

    Jie Gao, Leonidas J. Guibas, and An Thai Nguyen. Deformable spanners and applications. Comput. Geom. , 35(1-2):2--19, 2006. https://doi.org/10.1016/J.COMGEO.2005.10.001 doi:10.1016/J.COMGEO.2005.10.001

    2006 doi

  25. [33]

    Near optimal locality sensitive orderings in E uclidean space

    Zhimeng Gao and Sariel Har - Peled. Near optimal locality sensitive orderings in E uclidean space. In 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece , volume 293 of LIPIcs , pages 60:1--60:14. Schloss Dagstuhl - Leibniz-Zent...

    2024 doi

  26. [34]

    Improved algorithms for fully dynamic geometric spanners and geometric routing

    Lee - Ad Gottlieb and Liam Roditty. Improved algorithms for fully dynamic geometric spanners and geometric routing. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008 , pages 591--60...

    2008

  27. [35]

    An optimal dynamic spanner for doubling metric spaces

    Lee - Ad Gottlieb and Liam Roditty. An optimal dynamic spanner for doubling metric spaces. In Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings , volume 5193 of Lecture Notes in Computer Science , pages 478--489. Spri...

    2008 doi

  28. [36]

    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

    2006 doi

  29. [37]

    Geometric Approximation Algorithms

    Sariel Har- P eled. Geometric Approximation Algorithms . American Mathematical Society, USA, 2011. https://doi.org/10.1090/surv/173 doi:10.1090/surv/173

    2011 doi

  30. [38]

    A gap- ETH -tight approximation scheme for E uclidean TSP

    Sándor Kisfaludi-Bak, Jesper Nederlof, and Karol Węgrzycki. A gap- ETH -tight approximation scheme for E uclidean TSP . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 351--362, 2022. https://doi.org/10.1109/FOCS52979.2021.00043 doi:10.1109...

    2021

  31. [39]

    Mark Keil

    J. Mark Keil. Approximating the complete E uclidean graph. In SWAT 88 , pages 208--213, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-19487-8_23 doi:10.1007/3-540-19487-8_23

    1988 doi

  32. [40]

    Hyperbolic intersection graphs and (quasi)-polynomial time

    S \' a ndor Kisfaludi - Bak. Hyperbolic intersection graphs and (quasi)-polynomial time. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020 , pages 1621--1638. SIAM , 2020. https://doi.org/10.1137/1.97816...

    2020 doi

  33. [41]

    u rich, Switzerland , volume 164 of LIPIcs , pages 55:1--55:15. Schloss Dagstuhl - Leibniz-Zentrum f \

    S \' a ndor Kisfaludi - Bak. A quasi-polynomial algorithm for well-spaced hyperbolic TSP . In 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Z \" u rich, Switzerland , volume 164 of LIPIcs , pages 55:1--55:15. Schloss Dagstuhl - Leibniz-Ze...

    2020 doi

  34. [42]

    Robert Krauthgamer and James R. Lee. Algorithms on negatively curved spaces. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006) , pages 119--132. IEEE Computer Society, 2006. https://doi.org/10.1109/FOCS.2006.9 doi:10.1109/FOCS.2006.9

    2006 doi

  35. [43]

    Philip N. Klein. A subset spanner for planar graphs, with application to subset TSP . In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006 , pages 749--756. ACM , 2006. https://doi.org/10.1145/1132516.1132620 doi:10.1145/113...

    2006

  36. [44]

    Hyperbolic geometry of complex networks

    Dmitri Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Mari \'a n Bogun \'a . Hyperbolic geometry of complex networks. Physical Review E , 82(3):036106, 2010. https://doi.org/10.1103/PhysRevE.82.036106 doi:10.1103/PhysRevE.82.036106

    2010 doi

  37. [45]

    A quadtree, a S teiner spanner, and approximate nearest neighbours in hyperbolic space

    S \' a ndor Kisfaludi - Bak and Geert van Wordragen. A quadtree, a S teiner spanner, and approximate nearest neighbours in hyperbolic space. In 40th International Symposium on Computational Geometry, SoCG 2024, June 11-14, 2024, Athens, Greece , volume 293 of LIPIcs , pages 68...

    2024 doi

  38. [46]

    Dynamic locality sensitive orderings in doubling metrics

    An La and Hung Le. Dynamic locality sensitive orderings in doubling metrics. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025 , pages 1178--1189. ACM , 2025. https://doi.org/10.1145/3717823.3718209 doi:10.1145...

    2025

  39. [47]

    A focus+context technique based on hyperbolic geometry for visualizing large hierarchies

    John Lamping, Ramana Rao, and Peter Pirolli. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In Proceedings of the SIGCHI conference on Human factors in computing systems , pages 401--408, 1995. https://doi.org/10.1145/223904.223956 do...

    1995

  40. [48]

    Truly optimal E uclidean spanners

    Hung Le and Shay Solomon. Truly optimal E uclidean spanners. SIAM Journal on Computing , pages FOCS19 \-- 135--FOCS19 \-- 199, 2022. https://doi.org/10.1137/20M1317906 doi:10.1137/20M1317906

    2022 doi

  41. [49]

    Learning continuous hierarchies in the L orentz model of hyperbolic geometry

    Maximilian Nickel and Douwe Kiela. Learning continuous hierarchies in the L orentz model of hyperbolic geometry. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 , volume 80 of Proceedings of Machine Learning Research , pages 3776--3785. PMLR ...

    2018

  42. [50]

    Voronoi diagrams on the sphere

    Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong. Voronoi diagrams on the sphere. Computational Geometry , 23(2):183--194, 2002. https://doi.org/10.1016/S0925-7721(02)00077-9 doi:10.1016/S0925-7721(02)00077-9

    2002 doi

  43. [51]

    Geometric spanner networks

    Giri Narasimhan and Michiel Smid. Geometric spanner networks . Cambridge University Press, 2007. https://doi.org/10.1017/CBO9780511546884 doi:10.1017/CBO9780511546884

    2007 doi

  44. [52]

    Embeddings and near-neighbor searching with constant additive error for hyperbolic spaces

    Eunku Park and Antoine Vigneron. Embeddings and near-neighbor searching with constant additive error for hyperbolic spaces. Computational Geometry , 126:102150, 2025. https://doi.org/10.1016/j.comgeo.2024.102150 doi:10.1016/j.comgeo.2024.102150

    2025

  45. [53]

    Hyperbolic deep neural networks: A survey

    Wei Peng, Tuomas Varanka, Abdelrahman Mostafa, Henglin Shi, and Guoying Zhao. Hyperbolic deep neural networks: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence , 44(12):10023--10044, 2022. https://doi.org/10.1109/TPAMI.2021.3136921 doi:10.1109/TPAMI.202...

    2022

  46. [54]

    Transitive-closure spanners: A survey

    Sofya Raskhodnikova. Transitive-closure spanners: A survey. In Property Testing - Current Research and Surveys , volume 6390 of Lecture Notes in Computer Science , pages 167--196. Springer, 2010. https://doi.org/10.1007/978-3-642-16367-8_10 doi:10.1007/978-3-642-16367-8_10

    2010 doi

  47. [55]

    Fully dynamic geometric spanners

    Liam Roditty. Fully dynamic geometric spanners. Algorithmica , 62(3-4):1073--1087, 2012. https://doi.org/10.1007/S00453-011-9504-7 doi:10.1007/S00453-011-9504-7

    2012 doi

  48. [56]

    spanners

    Satish Rao and Warren D. Smith. Approximating geometrical graphs via "spanners" and "banyans". In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998 , pages 540--550. ACM , 1998. https://doi.org/10.1145/276698.2768...

    1998

  49. [57]

    The weak gap property in metric spaces of bounded doubling dimension

    Michiel Smid. The weak gap property in metric spaces of bounded doubling dimension. In Efficient Algorithms, Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday , volume 5760 of Lecture Notes in Computer Science , pages 275--289. Springer, 2009. https://doi....

    2009 doi

  50. [58]

    Shavitt and T

    Y. Shavitt and T. Tankel. On the curvature of the internet and its usage for overlay construction and distance estimation. In IEEE INFOCOM 2004 , volume 1, page 384, 2004. https://doi.org/10.1109/INFCOM.2004.1354510 doi:10.1109/INFCOM.2004.1354510

    2004 arXiv

  51. [59]

    Bypassing the embedding: algorithms for low dimensional metrics

    Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In 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

    2004

  52. [60]

    Parallel shortcutting of rooted trees

    Mikkel Thorup. Parallel shortcutting of rooted trees. J. Algorithms , 23(1):139--159, 1997. https://doi.org/10.1006/JAGM.1996.0829 doi:10.1006/JAGM.1996.0829

    1997

  53. [61]

    Metric embedding, hyperbolic space, and social networks

    Kevin Verbeek and Subhash Suri. Metric embedding, hyperbolic space, and social networks. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry , SOCG'14, page 501–510, New York, NY, USA, 2014. Association for Computing Machinery. https://doi.org/10.1145/25...

    2014

Pith tools

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