Abstract
We present a simple framework to compute hyperbolic Voronoi diagrams of finite point sets as affine diagrams. We prove that bisectors in Klein's non-conformal disk model are hyperplanes that can be interpreted as power bisectors of Euclidean balls. Therefore our method simply consists in computing an equivalent clipped power diagram followed by a mapping transformation depending on the selected representation of the hyperbolic space (e.g., Poincaré conformal disk or upper-plane representations). We discuss extensions of this approach to weighted and k-order diagrams, and describe their dual triangulations. Finally, we consider two useful primitives on the hyperbolic Voronoi diagrams for designing tailored user interfaces of an image catalog browsing application in the hyperbolic disk: (1) finding nearest neighbors, and (2) computing smallest enclosing balls.
Introduction: The Challenge of Hyperbolic Geometry
Voronoi diagrams are fundamental tools in computational geometry used to partition space into regions based on proximity to a set of points. While well-understood in Euclidean space, they are much harder to handle in hyperbolic geometry—a non-Euclidean geometry often used to visualize large hierarchies or complex networks because it "expands" exponentially.
In the popular Poincaré disk model, the "straight lines" (geodesics) and Voronoi bisectors are curved arcs, making them computationally expensive to calculate and manipulate, especially in higher dimensions. Previous attempts to solve this were often limited to 2D or relied on complex, specialized algorithms. This paper seeks a unified way to make hyperbolic Voronoi diagrams as easy to compute as their Euclidean counterparts.
Methodology: The Klein Model and Power Diagrams
The authors’ breakthrough lies in switching the mathematical "lens" used to view hyperbolic space. Unlike the conformal Poincaré model, the Klein projective disk model represents hyperbolic geodesics as straight Euclidean line segments.
Linear Bisectors
The paper proves that the bisector between two points in the Klein model is a hyperplane (a flat surface). This means the resulting Voronoi diagram is "affine"—it consists of cells with flat faces. Since the diagram is affine, it can be mapped to a Euclidean power diagram (also known as a Laguerre diagram). In a power diagram, each point is treated as a ball with a specific radius.
Algorithmic Efficiency
By providing explicit formulas to transform a hyperbolic point into a Euclidean ball, the method allows any standard Euclidean geometry library (like CGAL) to compute the diagram. This reduction ensures optimal complexity: $O(n \log n + n^{\lceil d/2 \rceil})$, the theoretical optimum for building Voronoi diagrams in $d$ dimensions. One-to-one conversion formulas are then used to move the resulting diagram between the Klein model, the Poincaré disk, and the Poincaré upper-half plane.
Practical Applications: Image Catalog Browsing
To demonstrate the practical utility of this method, the authors developed an interactive image catalog browsing application. Images retrieved via the Yahoo! API were embedded into 2D hyperbolic space using Sammon clustering to preserve relative distances.
The framework enables two critical UI primitives:
- Nearest Neighbor Search: Finding the closest image to a user's mouse click in $O(\log n)$ time.
- Smallest Enclosing Ball: Efficiently finding the smallest hyperbolic circle that contains a group of selected images, allowing the interface to "re-center" and zoom smoothly using Möbius transformations.
Conclusion
By leveraging the Klein model to "straighten" hyperbolic boundaries, this research provides a robust and efficient path for computing Voronoi diagrams in non-Euclidean spaces. This approach simplifies complex geometric tasks into standard Euclidean operations, facilitating the development of advanced visualization tools for hierarchical data.
Summary updated