CS Paper Radar

The Hyperbolic Surface Distance, Diameter, and Dirichlet Problems

Vincent Despre, Auguste Gezalyan, Marc Pouget

cs.CG ·submitted 2026-09-09 00:06 UTC · v2

Abstract

Despite the prominence of hyperbolic surfaces in mathematics, basic algorithmic questions about them, even computing the distance between two points, have remained open, leaving many features of these surfaces inaccessible. The classical machinery assumes a polyhedral structure absent on a smooth surface. We remove these obstacles. We begin with an efficient $O(g^2)$ algorithm for the distance between two points, where $g$ is the genus of the surface. Building on it, we obtain an $O(g^2 \log g)$ method for answering distance queries from a fixed source and, as a consequence, for recentering a Dirichlet domain around an arbitrary point. This understanding of distances on the surface then lets us approximate the diameter to within any $\eps$ in time $O(g^3 \log g / \eps^2)$. We further show that the diameter, a single real number encoding a great deal about the surface, is exactly computable. Its hyperbolic cosine is an algebraic number over the field encoding the coefficients of the hyperbolic isometries defining the surface.

Closest papers

Nearest neighbours by meaning across the whole index.

Computing an e-net of a closed hyperbolic surface

cs.CG math.GT ·2026-08-25 ·Vincent Delecroix, Vincent Despré, Camille Lanuel, Hugo Parlier, Monique Teillaud
similarity 0.66
Abstract

Hyperbolic surfaces are a fundamental object in mathematics and play an increasingly important role in computational geometry and topology. A key ingredient in the design of efficient algorithms on such surfaces is the availability of a geometric discretization of controlled complexity. In this paper, we present the first algorithm for constructing e-nets on hyperbolic surfaces starting from a fundamental polygon representation. Our approach is based on Delaunay refinement and relies on maintaining Delaunay triangulations through edge flips. The size of an e-net cannot be bounded solely as a function of the genus because of the presence of arbitrarily long collars around short geodesics. To overcome this difficulty, we introduce the notion of a pseudo e-net, which decomposes the surface into e-thin cylinders together with a Delaunay triangulation over an e-net of the remaining thick part. As applications, we obtain algorithms for computing the length spectrum of an e-thick hyperbolic surface and for computing the systole from a pseudo log(sqrt(2))-net. These results demonstrate that Delaunay-based discretizations provide a practical and versatile framework for algorithmic computations on hyperbolic surfaces.

0.45

Optimal Coresets for Hyperbolic Farthest-Point Queries via Ideal-Boundary Envelopes

cs.CG ·2026-10-01 ·Eunku Park
theory similarity 0.66
Abstract

We study coresets for farthest-point queries in hyperbolic space. Given a nonempty finite set $P \subset \mathbb{H}^D$ and $0<\varepsilon \le 1$, we seek a coreset $P_{\varepsilon} \subseteq P$ whose farthest distance from every query point underestimates that of $P$ by at most an additive $\varepsilon$ and retains at least a $1-\varepsilon$ fraction of it. For every fixed $D \ge 2$, we prove that the optimal worst-case coreset size is $Θ\bigl(\varepsilon^{-(D-1)/2}\bigr)$. Our main geometric ingredient is an exact reduction from hyperbolic queries to an upper envelope on the ideal boundary. In the hyperboloid model, each input point induces a positive boundary-score function whose logarithm gives its asymptotic distance offset along geodesic rays. We define the \emph{ideal-boundary envelope} as the pointwise maximum of these functions and prove that the supremum additive loss over all queries equals the maximum logarithmic gap between the input and coreset envelopes. For the upper bound, we move the minimum-enclosing-ball center to the origin and normalize the spatial coordinates, obtaining a bounded Euclidean point set whose boundary envelope is bounded away from zero. A standard Euclidean kernel then approximates all directional score maxima simultaneously, and the structure theorem yields both guarantees. For the lower bound, a spherical packing on a fixed-radius hyperbolic sphere, together with antipodal queries and the hyperbolic cosine law, makes every input point indispensable, matching the upper bound even for either guarantee separately.

0.37

Hyperbolic Sphericity

cs.CG ·2026-10-01 ·Thomas Bläsius, Lennart Großkreutz, Jean-Pierre von der Heydt
similarity 0.60
Abstract

The sphericity of a graph is the minimum dimension d such that the graph has an intersection representation of d-dimensional balls of equal radius. While sphericity has been studied in Euclidean space, we initiate the study of hyperbolic sphericity. The hyperbolic sphericity of a graph can be significantly smaller than its Euclidean counterpart, but, contrary to the Euclidean setting, depends strongly on the radius of the balls. We show that, if the radius of the balls can be chosen depending on the graph, the hyperbolic sphericity is upper bounded by the Euclidean sphericity. This extends a previous result for 2-dimensional hyperbolic space, i.e., uniform disk graphs, to arbitrary dimensions. Moreover, our proof is significantly simpler. If we fix the radius, i.e., do not make it dependent on the graph, we show that hyperbolic sphericity can be larger than Euclidean sphericity, but by at most 1. Additionally, we study how hyperbolic sphericity changes with the ball radius. We show that choosing a larger radius can substantially decrease the sphericity while increasing it by at most 1. We also provide a construction of a graph where the sphericity oscillates between different values as the radius increases. Besides being theoretically interesting, we note that these results are relevant for graph embeddings in machine learning, where one is interested in low-dimensional numeric representations of symbolic data like graphs.

0.28

Shaving Two Logs for Discrete and Continuous Fréchet Distance

cs.CG ·2026-10-12 ·Timothy M Chan, Isaac M Hair
similarity 0.59
Abstract

We revisit the classical computational geometry problem of computing the exact (discrete or continuous) Fréchet distance between two given polygonal curves with $n$ vertices in a constant dimension $d$. 1. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the discrete Fréchet distance problem, improving the previous $O((n^2/\log n)\log\log n)$ result by Agarwal, Ben Avraham, Kaplan, and Sharir [SODA'13]. 2. We present an $O((n^2/\log^2n)\log^2\log n)$-time deterministic algorithm for the decision version of the continuous Fréchet distance problem, improving the previous $O((n^2/\log n)\log^2\log n)$ result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^{1+μ}n)$ randomized result by Cheng and Huang [SODA'25] for a small unspecified constant $μ>0$ (which converges to 0 as $d$ increases). 3. Finally, we present an $O((n^2/\log^2 n)\log^{O(1)}\log n)$-time Las Vegas randomized algorithm for the continuous Fréchet distance problem, improving the previous $O(n^2\log^2\log n)$ randomized result by Buchin, Buchin, Meulemans, and Mulzer [SODA'14] and the recent $O(n^2/\log^μn)$-time randomized result claimed by Cheng and Huang [SODA'25]. Since these problems have near-quadratic OV-based conditional lower bounds and shaving of two log factors is the best that is known for similar, simpler problems such as longest common subsequence and edit distance, our results reach the natural limit of the current state of the art (up to $\log\log$ factors).

0.27

Upper and Lower Bounds on the Complexity of Unit-Distance Graph Realization in $\mathbb{Z}^d$

cs.CC ·2026-10-27 ·Eric Binnendyk
theory similarity 0.59
Abstract

It is known that the problem of recognizing the existence of a unit-distance realization in $\mathbb{Z}^d$ for a graph $G$ is NP-complete. Here, assuming ETH, we give a sub-exponential lower bound of $2^{Ω(\sqrt{n})}$ for this problem in $\mathbb{Z}^2$ and $2^{Ω(n^{2/3})}$ in $\mathbb{Z}^3$, and give an upper bound of $2^{O(n^{(d-1)/d} (\log n)^2)}$ for the time complexity with an explicit divide-and-conquer algorithm. This approach beats naive exhaustive search by a factor of $\tildeΩ(n^{1/d})$ in the exponent. For 2 and 3 dimensions, our upper and lower bounds match to within a logarithmic factor.

0.27

Finding the Farthest in High Dimensions: Dynamic Diameter and Farthest-Neighbor Search

cs.DS ·2026-11-12 ·Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.57
Abstract

We give algorithms for maintaining diameter in the dynamic model, and for answering farthest-neighbor queries on a fixed point set, in high-dimensional Euclidean space. For every fixed $1<c<\sqrt2$, update horizon $t$, and error probability $δ$, we maintain an actual factor-$c$ diameter pair with worst-case update time $n^{2/c^2-1}\text{poly}_c(d,\log(2nt/δ))$ and space $n^{2/c^2}\text{poly}_c(d,\log(2nt/δ))$. Here $n$ bounds the number of active point identities. The update exponent improves Indyk's SODA~2003 bound from $1/c^2$ to $2/c^2-1$, while the space exponent improves from $1+1/c^2$ to $2/c^2$. At $c=\sqrt{3/2}$, the update exponent decreases from $2/3$ to $1/3$. A separate construction achieves approximation exactly $\sqrt2$ with update time polynomial in $d$ and $\log(2nt/δ)$. With probability at least $1-δ$, every maintained answer during the first $t$ updates is correct, even when updates depend on all previous answers and random choices. A second construction improves the update exponent when the space exponent is close to one. On rational inputs, it has an always-correct variant with expected amortized update bounds over every fixed finite prefix of an adaptive execution, without an advance update horizon. The dynamic structures store a current answer, so reporting its two point identifiers takes constant time. The geometric method also gives static diameter algorithms and a farthest-neighbor structure for a fixed set that answers arbitrary adaptive queries. At approximation $\sqrt2-\varepsilon$, the diameter time is $n^{1+O(\varepsilon)}$, and the query time is $n^{O(\varepsilon)+o(1)}$ with near-linear preprocessing and space, up to polynomial input-parameter factors.

0.25

Extrinsic Curvature Estimation by Closest Point Projection of Rays

cs.CG math.DG ·2026-10-24 ·Liangchen Liu, Yen-Hsi Richard Tsai
similarity 0.57
Abstract · 45 pages, 9 figures

We propose a parametrization-free framework for estimating the second fundamental form and the principal curvatures of a submanifold of $\mathbb{R}^d$. The method uses the closest point projections of a few short random rays and recovers the curvature from the curves that these projections induce on the submanifold, without coordinate charts or local fitting. We analyze the geometry of the induced curves and characterize when they are geodesics. For hypersurfaces, these results give two algorithms with error bounds: a least squares reconstruction of the second fundamental form from the curvatures of the induced curves, and a direct estimate of all principal curvatures from the eigenvalues of a $d\times d$ matrix built from $d$ rays, which needs no normal information and costs $\mathcal{O}(d^3)$ besides the projections. In higher codimension, we can also recover the second fundamental form one normal direction at a time. On point clouds, where the projection becomes a nearest neighbor query, we bound the additional error. Experiments confirm the predicted rates for hypersurfaces in up to $128$ dimensions, for surfaces of codimension up to $98$, and on point clouds, demonstrating the effectiveness of the proposed framework in practice.

0.33

A quantitative tree-likeness bound from average hyperbolicity

cs.DS math.PRmath.COmath.MG ·2026-09-16 ·Joon-Hyeok Yim
theory similarity 0.57
Abstract · 13 pages, 3 figures. Added comments on ultrametric fitting corollary, and AI statements

Chatterjee and Sloman proved that a bounded measurable similarity function with sufficiently small average Gromov hyperbolicity admits a tree representation with small mean approximation error. Their argument uses a weighted version of Szemerédi's regularity lemma and does not yield explicit quantitative bounds. Here, we establish a tighter relation between average hyperbolicity and mean tree approximation error. For a similarity function $s:S\times S\to[0,b]$, we prove that $$\operatorname{Tree}(s) \leq (63/e)^{1/3} \sqrt[3]{b^2 \operatorname{Hyp}(s)} \leq 2.8512 \sqrt[3]{b^2 \operatorname{Hyp}(s)}.$$ The proof uses a simple pivoting construction inspired by \KwikCluster. We also discuss the optimal dependence on average hyperbolicity, including a square-root lower bound, and connections with ultrametric fitting.

0.28