# Voronoi Diagrams in the Hilbert Metric

arXiv: https://arxiv.org/abs/2112.03056 · HTML: https://mlsanity.com/paper/2112.03056/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2021.

## Built on by (most cited first, 4 of 4)

- [Non-linear Embeddings in Hilbert Simplex Geometry](https://mlsanity.com/paper/2203.11434/) (2022)
- [Hilbert geometry of the symmetric positive-definite bicone: Application to the geometry of the extended Gaussian family](https://mlsanity.com/paper/2508.14369/) (2025)
- [The Tempered Hilbert Simplex Distance and Its Application To Non-linear Embeddings of TEMs](https://mlsanity.com/paper/2311.13459/) (2023)
- [Classifiers in High Dimensional Hilbert Metrics](https://mlsanity.com/paper/2601.13410/) (2026)

## Abstract (arXiv)

The Hilbert metric is a distance function defined for points lying within a convex body. It generalizes the Cayley-Klein model of hyperbolic geometry to any convex set, and it has numerous applications in the analysis and processing of convex bodies. In this paper, we study the geometric and combinatorial properties of the Voronoi diagram of a set of point sites under the Hilbert metric. Given any convex polygon K bounded by m sides, we present two algorithms (one randomized and one deterministic) for computing the Voronoi diagram of an n-element point set in the Hilbert metric induced by K. Our randomized algorithm runs in O(m n + n (log n)(log m n)) expected time, and our deterministic algorithm runs in time O(m n log n). Both algorithms use O(m n) space. We show that the worst-case combinatorial complexity of the Voronoi diagram is Theta(m n).