PhD Defense: Computational Geometry in the Funk and Hilbert Metrics

The Hilbert metric is a generalization of the Cayley-Klein model of hyperbolic geometry to arbitrary convex bodies. It has applications in convex approximation, quantum information theory, machine learning, and real analysis. The Hilbert metric can be constructed as the average of the forward Funk and reverse Funk metrics, which are asymmetric distance functions with their own applications in convex approximation and real analysis. Despite the significance of these metrics, there has been little work on understanding the Hilbert and Funk metrics from a computational geometry perspective. This dissertation fills this gap by examining their fundamental geometric structure and provides efficient algorithms for geometric problems in these metrics.
In the Hilbert metric, we provide several contributions on 2-dimensional polygons with m sides and n sites. We characterize bisectors as piecewise conics and provide an O(mn log n) expected time algorithm for constructing Voronoi diagrams in the metric, matching the worst-case Θ(mn) complexity up to a logarithmic factor. We analyze the behavior of these diagrams in their dynamic setting and study their discontinuities. We present an O(n(log n + log^3 m)) expected time algorithm for Delaunay triangulations in the Hilbert metric. Unlike the Euclidean case, the Hilbert Delaunay triangulation does not cover the convex hull of the point set. We introduce the concept of the Hilbert hull to characterize what is actually covered and provide an O(nh log^2 m) time algorithm for computing it, where h is the number of boundary points on the hull.
We extend our analysis to the forward and reverse Funk metrics in d-dimensional elliptical cones and 3-dimensional polygonal cones. We prove that bisectors in these metrics consist of rays from the cone's apex and show a reduction proving the equivalence between d-dimensional Funk Voronoi diagrams and (d-1)-dimensional additively weighted Funk Voronoi diagrams. Leveraging this, we present an O(n^2+n^(⌈(d-1)/2⌉ +1)) time algorithm for d-dimensional elliptical cones and an O(mn log n) time algorithm for 3-dimensional polygonal cones. We also provide a complete characterization of when three sites admit circumcenters in 3-dimensional polygonal cones.