  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)$.
