Efficient algorithms compute distances and diameter on hyperbolic surfaces
The Hyperbolic Surface Distance, Diameter, and Dirichlet Problems
Computational Geometry
Summary
Measuring distances on curved surfaces called hyperbolic surfaces is a basic problem that was not solved efficiently before. The authors designed new algorithms that quickly find the shortest distance between two points on these surfaces, even when the surface is complex. They also created methods to answer many distance queries from one point and to approximate or exactly calculate the surface's diameter. Their work helps reveal important geometric features of these curved surfaces, which were hard to analyze before due to mathematical challenges.
What this means in practice
- •For geometric software developers: Integrate fast algorithms to compute distances and diameters for modeling hyperbolic surfaces in visualization and simulation tools.
- •For 3d graphics engineers: Use efficient distance queries on hyperbolic surfaces to improve rendering and navigation in virtual environments with curved geometries.
Authors
Vincent Despre, Auguste Gezalyan, Marc Pouget
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.