Department of Computer Science, University of Maryland, College Park, USA and
<EMAIL_ADDRESS>ORCID LATER Department of Computer Science, University of
Maryland, College Park, USA and https://www.cs.umd.edu/
mount/mount@umd.eduhttps://orcid.org/0000-0002-3290-8932 Auguste H. Gezalyan
and David M. Mount [100]ACM classification John Q. Open and Joan R. Access 2
42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016
December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Voronoi Diagrams in the Hilbert Metric

Auguste H. Gezalyan  David M. Mount

###### Abstract

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(mn+n(\log n)(\log mn))$ expected
time, and our deterministic algorithm runs in time $O(mn\log n)$. Both
algorithms use $O(mn)$ space. We show that the worst-case combinatorial
complexity of the Voronoi diagram is $\Theta(mn)$.

###### keywords:

Voronoi diagrams, Hilbert metric, convexity, randomized algorithms

##  1 Introduction

The Hilbert metric was introduced by David Hilbert in 1895 [12]. Given a
convex body $K$ in $d$-dimensional space, it defines a distance function
between any pair of points in the interior of $K$. (Definitions are presented
in Section 2.1.) The Hilbert geometry has a number of natural properties. For
example, geodesics in the Hilbert geometry are straight line segments.

It generalizes hyperbolic geometry by adapting the Cayley-Klein model of
hyperbolic geometry (on Euclidean balls) to any convex body. It is also
invariant under projective transformations. Hilbert geometry provides new
insights into classical questions from convexity theory. It also provides new
insights into the study of metric and differential geometries (such as Finsler
geometries). An excellent resource on the Hilbert geometries is the handbook
on Hilbert geometry by Papadopoulos and Troyanov [17].

We came to consider the Hilbert geometry because of its relevance to the topic
of convex approximation. Efficient approximations of convex bodies have been
applied to a wide range of applications, including approximate nearest
neighbor searching both in Euclidean space [6] and more general metrics [1],
optimal construction of $\varepsilon$-kernels [4], solving the closest vector
problem approximately [9, 19, 10, 14], computing approximating polytopes with
low combinatorial complexity [5, 3]. These works all share one thing in
common—they approximate a convex body by covering it with elements that behave
much like metric balls. These covering elements go under various names:
Macbeath regions, Macbeath ellipsoids, Dikin ellipsoids, and
$(2,\varepsilon)$-covers. While these all behave like metric balls, the
question is in what metric space? Abdelkader and Mount showed that these
shapes are, up to constant factors, equivalent to Hilbert balls [2]. Thus, a
deeper understanding of how to compute within the Hilbert geometry can lead in
a principled way to a deeper understanding of convex approximation.

In spite of its obvious appeals, there has been remarkably little work the
design of algorithms in the Hilbert geometry on convex polygons and polytopes.
One notable exception is the work of Nielsen and Shao, which investigates
properties and efficient construction of Hilbert balls in convex polygons
[15].

In this paper, we investigate perhaps the most fundamental computational
question one might ask about a metric geometry: How to construct the Voronoi
diagram of a set of point sites in the plane? Given any convex polygon $K$
bounded by $m$ sides, we present two algorithms for computing the Voronoi
diagram of an $n$-element point set in the Hilbert metric induced by $K$. The
first is a randomized incremental algorithm, which runs in $O(mn+n(\log
n)(\log mn))$ expected time. The second is a deterministic algorithm based on
divide-and-conquer, which runs in time $O(mn\log n)$. Both algorithms use
$O(mn)$ space. We show that the worst-case combinatorial complexity of the
Voronoi diagram is $\Theta(mn)$, so both algorithms are worst-case optimal up
to logarithmic factors.

##  2 Preliminaries

Throughout, a _convex body_ $K$ in $\mathbb{R}^{d}$ is a closed, compact,
full-dimensional convex set in $\mathbb{R}^{d}$. Let $\partial K$ and
$\operatorname{int}(K)$ denote its boundary and interior, respectively. Given
points $p,q\in\mathbb{R}^{d}$, let $\|p-q\|$ denote the Euclidean distance
between these points. Given two distinct points $p,q\in K$, let $\chi(p,q)$
denote the _chord_ defined as the intersection of the line passing through $p$
and $q$ with $K$.

###  2.1 Funk and Hilbert Metrics

Recall that a _metric space_ is a pair $(\mathbb{X},d)$ where $\mathbb{X}$ is
a set and $d$ is a function
$d:\mathbb{X}\times\mathbb{X}\rightarrow\mathbb{R}^{\geq 0}$, which, for all
$x,y,z\in\mathbb{X}$ satisfies

  * •

$d(x,y)=0~{}\Leftrightarrow~{}x=y$

  * •

$d(x,y)=d(y,x)$

  * •

$d(x,y)\leq d(x,z)+d(z,y)$

Before defining the Hilbert metric, it is convenient to define a simpler
(asymmetric) distance function called the _Funk weak metric_.

######  Definition 2.1 (Funk weak metric).

Given a convex body $K$ in $\mathbb{R}^{d}$ and two distinct points
$p,q\in\operatorname{int}(K)$, let $y$ denote point where a ray shot from $p$
to $q$ intersects $\partial K$. Define the _Funk weak metric_ to be

$F_{K}(p,q)~{}=~{}\ln\frac{\|p-y\|}{\|q-y\|},$

and define $F_{K}(p,p)=0$ (see Figure 1(a)).

Figure 1: (a) The Funk weak metric and (b) the Hilbert metric.

Observe that in the limit as $q$ approaches $y$ along the chord $\chi(p,y)$
the Funk distance increases to $+\infty$, and thus, the boundary is infinitely
far away from any interior point of $K$. The Funk weak metric is not
symmetric, but it satisfies the other two properties of a metric. (For a proof
of the triangle inequality, see Yamada [21].) Symmetrizing this yields the
Hilbert metric [12].

######  Definition 2.2 (Hilbert metric).

Given a convex body $K$ in $\mathbb{R}^{d}$ and two distinct points
$p,q\in\operatorname{int}(K)$, let $x$ and $y$ denote endpoints of the chord
$\chi(p,q)$, so that the points are in the order $\langle x,p,q,y\rangle$.
Define the _Hilbert metric_ to be

$H_{K}(p,q)~{}=~{}\frac{F_{K}(p,q)+F_{K}(q,p)}{2}~{}=~{}\frac{1}{2}\ln\frac{\|p-y\|\|q-x\|}{\|q-y\|\|p-x\|},$

and define $H_{K}(p,p)=0$ (see Figure 1(b)).

This is indeed a metric since it satisfies the triangle inequality. Further,
if $q$ lies on the line segment between $p$ and $r$, then
$H_{K}(p,q)+H_{K}(q,r)=H_{K}(p,r)$. As in the Funk weak metric, the boundary
of $K$ is infinitely far away from any interior point. Observe that the
quantity in the $\ln$ term in the definition of Hilbert is the cross ratio of
$(p,q;y,x)$. It follows that the Hilbert metric is invariant under projective
transformations. It is well known that straight line segments are geodesics in
the Hilbert metric, but generally there may be multiple shortest paths between
two points, and hence geodesics need not be line segments (see, e.g., [7]).
For further information, see the first chapters of the handbook on Hilbert
geometry by Papadopoulos and Troyanov [17].

###  2.2 Balls in the Hilbert Metric

Given a convex body $K$ in $\mathbb{R}^{d}$, $p\in\operatorname{int}(K)$, and
$r\geq 0$, let

$B_{K}(p,r)~{}=~{}\\{q\in K\,:\,H_{K}(p,q)\leq r\\}$

denote the _Hilbert ball_ of radius $r$ centered at $p$. Nielsen and Shao [15]
provided a characterization of Hilbert balls when $K$ is an $m$-sided convex
polygon in $\mathbb{R}^{2}$, showing that the ball is a polygon bounded by at
most $2m$ sides. We generalize their result to arbitrary convex polytopes in
$\mathbb{R}^{d}$. This provides an alternative (and more elementary) proof
that Hilbert balls are convex (also proved in [16, 20]).

######  Lemma 2.3.

Given any convex polytope $K$ in $\mathbb{R}^{d}$ bounded by $m$ facets,
$p\in\operatorname{int}(K)$, and $r\geq 0$, $B_{K}(p,r)$ is a convex polytope
bounded by at most $m(m-1)$ facets. If $d=2$, then $B_{K}(p,r)$ is a convex
polygon bounded by at most $2m$ sides.

######  Proof 2.4.

For now, let us take $K$ to be any convex body (not necessarily a polytope).
Let $\mathbb{U}^{d}$ denote the set of all unit vectors in $\mathbb{R}^{d}$.
For each $u\in\mathbb{U}^{d}$, consider the ray emanating from $p$ in
direction $u$, and define $q_{r}(u)\in K$ to be the (unique) point along this
ray whose Hilbert distance from $p$ is $r$. Clearly, the boundary of
$B_{K}(p,r)$ is just the set of points $q_{r}(u)$ over all
$u\in\mathbb{U}^{d}$.

For any $u\in\mathbb{U}^{d}$, let $h(u)$ denote any supporting hyperplane of
$K$ at the point where the ray emanating from $p$ in the direction $u$
intersects the boundary of $K$ (see Figure 2(a)). Define $h(-u)$ analogously
for the ray emanating from $p$ in the direction $-u$. Let $g(u)$ ($=g(-u)$)
denote the $(d-2)$-dimensional affine subspace where $h(u)$ and $h(-u)$
intersect. (To avoid dealing with objects at infinity, let us assume that
$h(u)$ and $h(-u)$ are not parallel, which we can achieve through an
infinitesimal perturbation of $K$.) Let $h_{r}(u)$ denote the
$(d-1)$-hyperplane passing through both $g(u)$ and $q_{r}(u)$, and define
$h_{r}(-u)$ analogously for $q_{r}(-u)$. (These are both well defined because
neither $q_{r}(u)$ nor $q_{r}(-u)$ can lie on $g(u)$.)

Figure 2: Proof of Lemma 2.3 (showing just the intersection with the plane
$f$).

To simplify matters, let us restrict attention to the $2$-dimensional affine
subspace $f$ that is orthogonal to $g(u)$ and passes through $p$. It follows
that $g(u)\cap f$ is a single point, which we may take to be the origin. The
respective intersections of $h(u)$, $h(-u)$, $h_{r}(u)$, and $h_{r}(-u)$ with
$f$ are all lines that pass through the origin (since they all contain
$g(u)$). Let $C(u)$ denote the convex cone on $f$ whose apex is at the origin
and is bounded by $h(u)$ and $h(-u)$ (see Figure 2(b)). It follows from basic
properties of projective geometry that every line passing through $p$ on this
plane is cut by $h(u)$, $h(-u)$, $h_{r}(u)$, and $p$ into four points that
share the same cross ratio. This implies that every point on $h_{r}(u)$ is at
Hilbert distance $r$ from $p$. The same applies symmetrically to $h_{r}(-u)$,
and therefore the sub-cone of $C(u)$ bounded by $h_{r}(u)$ and $h_{r}(-u)$ is
just the Hilbert ball of radius $r$ centered at $p$ for $C(u)$. (This was
observed by Nielsen and Shao in their analysis of the two-dimensional case.)
Let us call this sub-cone $C_{r}(u)$.

We can now extend this observation back to the full $d$-dimensional space, by
considering the Minkowski sum $f\oplus g(u)$ (that is, the set resulting from
pairwise sums of points of $f$ and points of $g(u)$). Let
$\widehat{C}(u)=C(u)\oplus g(u)$ and let $\widehat{C}_{r}(u)=C_{r}(u)\oplus
g(u)$. We assert that $\widehat{C}_{r}(u)$ is the Hilbert ball of radius $r$
centered at $p$ with respect to $\widehat{C}(u)$. This follows because ratios
of lengths are preserved under orthogonal projection, and so any chord of
$\widehat{C}(u)$ that passes through $p$ is cut by $\widehat{C}_{r}(u)$ is the
same proportions as is the orthogonal projection of the chord onto $f$, which
we have shown above yields Hilbert distances equal to $r$.

Note that $p\in K\subseteq\widehat{C}_{r}(u)$, and therefore Hilbert distances
from $p$ in $\widehat{C}_{r}(u)$ are at least as large as they are in $K$.
Therefore, for all $u\in\mathbb{U}^{d}$,
$B_{K}(p,r)\subseteq\widehat{C}_{r}(u)$, and hence

$B_{K}(p,r)~{}\subseteq~{}\bigcap\nolimits_{u\in\mathbb{U}^{d}}\widehat{C}_{r}(u).$

On the other hand, by definition of $\widehat{C}_{r}(u)$, we know that
$\widehat{C}_{r}(u)$ and $B_{K}(p,r)$ both cover the exactly the same portion
of the chord parallel to $u$ passing through $p$. Since these chords cover all
the boundary points of $B_{K}(p,r)$, we have

$B_{K}(p,r)~{}=~{}\bigcap\nolimits_{u\in\mathbb{U}^{d}}\widehat{C}_{r}(u).$

Clearly, $\widehat{C}_{r}(u)$ is convex for any $u\in\mathbb{U}^{d}$, and
because convex sets are closed under (infinite) intersections, $B_{K}(p,r)$ is
also convex, as desired.

Suppose now that $K$ is a convex polytope in $\mathbb{R}^{d}$ bounded by $m$
$(d-1)$-dimensional facets. We say that two facets $f^{+}$ and $f^{-}$ are
_complimentary_ if there exists $u\in\mathbb{U}^{d}$ such that the rays
emanating from $p$ in the directions $u$ and $-u$ hit $f+$ and $f^{-}$,
respectively (see Figure 2(c)). We can partition the elements of
$\mathbb{U}^{d}$ into equivalence classes according to the associated
complimentary pair. All the unit vectors $u$ from any one equivalence class
share the same supporting hyperplanes $h(u)$ and $h(-u)$, and therefore all of
them contribute the same two facets the boundary of $B_{K}(p,r)$. Clearly,
there are at most $\binom{m}{2}$ complimentary facet pairs, and hence there
are at most $2\binom{m}{2}=m(m-1)$ facets bounding $B_{K}(p,r)$, as desired.

When $d=2$ and $K$ is an $m$-sided convex polygon, the number of complimentary
facets (or complimentary edges) is at most $2m$. To see this, consider the
chords $\chi(v,p)$ for each each of the $m$ vertices of $K$. This partitions
$\partial K$ into at most $2m$ boundary intervals, each corresponding to a
different complimentary pair. This completes the proof.

##  3 Characterization of Voronoi Diagrams in the Hilbert Metric

Using our understanding of Hilbert balls we can characterize Voronoi diagrams
in the Hilbert Metric. Throughout, let $K$ denote a convex polygon in
$\mathbb{R}^{2}$, and unless otherwise stated, distances will be in the
Hilbert metric induced by $K$, which we denote simply by $d(\cdot,\cdot)$. Let
$S$ denote a set of $n$ points lying within $K$’s interior, which we call
_sites_.

For $p\in S$, define its _Voronoi cell_ to be

$V(p)~{}=~{}V_{S}(p)~{}=~{}\big{\\{}q\in K\,:\,d(q,p)\leq
d(q,p^{\prime}),\,\forall p^{\prime}\in S\setminus\\{p\\}\big{\\}}.$

Although points on $K$’s boundary are infinitely far from points in $K$’s
interior, we can compare the relative distances a fixed boundary point and two
interior points by considering the limit as an interior point approaches this
boundary point. The _Voronoi diagram_ of $S$ in the Hilbert metric induced by
$K$, denoted $\operatorname{Vor}_{K}(S)$, is the cell complex of $K$ induced
by the Voronoi cells $V(p)$ for all $p\in S$. We assume that the points of $S$
are in general position, and in particular, the line passing through any pair
of sites of $S$ and the lines extending any two edges of $K$ are not
coincident at a common point (including all three being parallel). When this
happens, the bisectors separating Voronoi cells can widen into 2-dimensional
regions.

Recall that $R\subseteq\mathbb{R}^{d}$ is a _star_ (or is _star-shaped_) with
respect to a point $p\in R$ if for each $q\in R$, the line segment $pq$ lies
within $R$. We next show that Hilbert Voronoi cells satisfy this.

######  Lemma 3.1.

Voronoi cells in the Hilbert Metric are stars with respect to their defining
sites.

######  Proof 3.2.

If this were not the case, there would exist a site $p$ and points $x,y\in K$
such that $x\in V(p)$, $y\notin V(p)$, and $y$ lies on the line segment $px$.
By collinearity, $d(p,x)=d(p,y)+d(x,y)$. Letting $q$ be the closest site to
$y$, we have $d(q,y)<d(p,y)$ and $d(p,x)\leq d(q,x)$. Combining these we have
$d(q,x)+d(p,y)>d(q,y)+d(p,x)$, or equivalently $d(q,x)>d(q,y)+d(x,y)$. But
this violates the triangle inequality, yielding a contradiction.

###  3.1 Bisectors in the Hilbert Metric

Given two sites $p,p^{\prime}\in\operatorname{int}(K)$, we define their
Hilbert bisector, denoted the _$(p,p^{\prime})$ -bisector_, to be $\\{z\in
K:d_{K}(z,p)=d_{K}(z,p^{\prime})\\}$. We will explore the conditions for a
point $z$ to lie on the bisector. Let $x$ and $y$ denote the endpoints of the
chord $\chi(z,p)$ and define $x^{\prime}$ and $y^{\prime}$ analogously for
$\chi(z,p^{\prime})$. Label these points in the order $\langle x,z,p,y\rangle$
and $\langle x^{\prime},z,p^{\prime},y^{\prime}\rangle$ (see Figure 3(a)).
Finally, let $\ell_{x}$, $\ell_{p}$, and $\ell_{y}$ denote the lines passing
through the line segments $xx^{\prime}$, $pp^{\prime}$ and $yy^{\prime}$,
respectively. If these three lines are coincident on some point $q$ then by
basic properties of projective geometry, the cross ratios $(z,p;y,x)$ and
$(z,p^{\prime};y^{\prime},x^{\prime})$ are equal. It follows that
$d_{K}(z,p)=d_{K}(z,p^{\prime})$, and hence $z$ is on the bisector. If not,
then the cross ratios are different and the Hilbert distances are different.
Observe that as $z$ approaches the boundary of $K$ (on the same side of
$\ell_{p}$ as $\ell_{x}$), the points $z$, $x$, and $x^{\prime}$ converge on a
common point on $\partial K$, and $\ell_{x}$ approaches a support line for $K$
at this point (see Figure 3(b)). Thus, we obtain the following
characterization of bisector points.

Figure 3: Conditions for a point $z$ to lie on the Hilbert bisector between
sites $p$ and $p^{\prime}$.

######  Lemma 3.3.

Given a convex body $K$ in $\mathbb{R}^{2}$, sites
$p,p^{\prime}\in\operatorname{int}(K)$ and any other point
$z\in\operatorname{int}(K)$, $z$ lies on the $(p,p^{\prime})$-bisector if any
only if lines $\ell_{x}$, $\ell_{p}$, and $\ell_{y}$ (defined above) are
coincident. Further, a point $x\in\partial K$ is on the Hilbert bisector if
the coincidence holds when $\ell_{x}$ is any support line at $x$.

When $K$ is an $m$-sided convex polygon in $\mathbb{R}^{2}$, we can provide a
more precise characterization of the bisectors. Given two sites
$p,p^{\prime}\in\operatorname{int}(K)$, we will show below that the
$(p,p^{\prime})$-bisector is a piecewise curve where the pieces can be
described as rational parametric functions of bounded degree. Assuming this
for now, we can characterize the breakpoints in this curve. Letting
$\\{v_{1},\ldots,v_{m}\\}$ denote $K$’s vertices, the $2m$ chords
$\chi(v_{i},p)$ subdivide $K$ into $2m$ triangular regions, which we call
$p$’s _sectors_ with respect to $K$ (see Figure 4(a)111Throughout, figures
showing Hilbert bisectors are illustrative of general concepts and are not
geometrically accurate. ).

Figure 4: (a) The sectors of $p$ with respect to $K$ and (b) a (not
geometrically accurate) rendering of the Hilbert bisector between $p$ and
$p^{\prime}$.

###  3.2 Bisector Segments and Combinatorial Complexity

For each point $z$ on the $(p,p^{\prime})$-bisector, let $e$ and $f$ denote
the edges where the endpoints of chord $\chi(z,p)$ intersect $\partial K$, and
let $e^{\prime}$ and $f^{\prime}$ denote the corresponding edges of
$\chi(z,p^{\prime})$. Observe that the pair $(e,f)$ is uniquely determined by
the sector of $p$ containing $z$, and the pair $(e^{\prime},f^{\prime})$ is
similarly determined by the sector of $p^{\prime}$ containing $z$. Therefore,
the points of the $(p,p^{\prime})$-bisector can be grouped into a discrete set
of equivalence classes based on their sector memberships with respect to $p$
and $p^{\prime}$ (see Figure 4(b)). We refer to these as _bisector segments_.
Observe that by the star-shaped nature of Voronoi cells, as we travel along
the bisector, we encounter the (up to $2m$) sectors of $p$ in cyclic order
(say clockwise as in the figure), and we visit (up to $2m$) the sectors of
$p^{\prime}$ in the opposite cylic order (counterclockwise). We will see below
that, each bisector segment can be described by a simple parametric function
involving $p$, $p^{\prime}$, and the four edges defining the equivalence
class. Star-shapedness implies that the bisector is simply connected.
Combining the total number of sectors involved for each site, we have:

######  Lemma 3.4.

Given an $m$-sided convex polygon $K$ in $\mathbb{R}^{2}$ and sites
$p,p^{\prime}\in\operatorname{int}(K)$, the $(p,p^{\prime})$-bisector is a
simply connected piecewise curve consisting of at most $4m$ bisector segments.

Given a set of $n$ sites $S$ in $K$, the Voronoi diagram consists of a
collection of $n$ Voronoi cells. The intersection of two cells $V(p)$ and
$V(p^{\prime})$ (if nonempty) is a portion of $(p,p^{\prime})$-bisector, which
call a _Voronoi edge_. As shown in the above lemma, each such edge is composed
of at most $4m=O(m)$ bisector segments. A cell’s boundary may also contain a
portion of the boundary of $K$. The intersection of two Voronoi edges (if
nonempty) is a _Voronoi vertex_. Because the diagram is a planar graph, we
have the following bounds by a straightforward application of Euler’s formula.

######  Lemma 3.5.

Given an $m$-sided convex polygon $K$ in $\mathbb{R}^{2}$ and a set of $n$
sites $S$ in $K$, $\operatorname{Vor}_{K}(S)$ has $n$ Voronoi cells, at most
$3n$ Voronoi edges, and at most $2n$ Voronoi vertices. Each Voronoi edge
consists of at most $4m$ bisector segments. Therefore, the entire diagram has
total combinatorial complexity $O(mn)$. The average number of Voronoi edges
per cell is $O(1)$, and the average number of bisector segments per cell is
$O(m)$.

The following lemma shows that the bound on the combinatorial complexity is
tight in the worst case.

######  Lemma 3.6.

There exists a convex polygon $K$ with $m$ sides and a set $S$ of $n$ sites
within $K$ such that $\operatorname{Vor}_{K}(S)$ has combinatorial complexity
$\Omega(mn)$.

######  Proof 3.7.

We start the construction with an axis parallel rectangle $R$ that is slightly
taller than wide, and the set $S$ consists of $n$ points positioned on a short
horizontal line segment near the center of this rectangle (see Figure 5(a)).
(This violates our general position assumptions, but the construction works if
we perturb the sides of the rectangle.) Also, create a set of $m-4$ points
$V=\\{v_{1},\ldots,v_{m-4}\\}$ along $R$’s left edge. We can adjust the
spacing of points of $V$ and $S$ and the side lengths of $R$ so that there
exists a diamond shape (shaded in orange in the figure) so that for any point
$q$ in this region, the chord $\chi(v_{i},q)$ intersects the boundary of $R$
along its vertical sides. Observe that within the diamond, each consecutive
pair of sites contributes an edge to the Voronoi diagram, which is easily
verified to be a vertical line segment within the diamond.

Figure 5: Proof of Lemma 3.6.

To form $K$, we bend the left side of the rectangle out infinitesimally (see
Figure 5(b)) so the points of $V$ become vertices of a convex polygon. The
bending does not alter the shape of the Voronoi edges significantly, except to
break each edge up into multiple arcs.

We assert that each consecutive pair of points $p,p^{\prime}\in S$ contributes
at least $m-4$ arcs to the Voronoi diagram. To see why, observe that there are
$m-4$ sectors about $p$ and $p^{\prime}$, and vertical line passing between
$p$ and $p^{\prime}$ intersects the boundaries between these sectors (see the
red curve in Figure 5(c)). Due to the infinitesimal bending of $R$’s left
side, each crossing produces a new segment on the bisector. Since there are
$n-1$ consecutive pairs of sites, the total complexity of
$\operatorname{Vor}_{K}(S)$ is at least $(m-4)(n-1)=\Omega(mn)$, as desired.

###  3.3 Bisector Segments

Next, let us consider the exact formulation of each bisector segment. Again,
let $p$ and $p^{\prime}$ be sites, let $z$ denote some point on the
$(p,p^{\prime})$-bisector, and let $e$ and $f$ (resp., $e^{\prime}$ and
$f^{\prime}$) be the edges of $K$ bounding $\chi(z,p)$ (resp.,
$\chi(z,p^{\prime})$). Let us label these so they encounter the chord in the
order $\langle e,z,p,f\rangle$ (resp., $\langle
e^{\prime},z,p^{\prime},f^{\prime}\rangle$). Describing the bisector is messy,
given that it depends on the coordinates/coefficients of $p$, $p^{\prime}$,
$e$, $f$, $e^{\prime}$, and $f^{\prime}$, for a total of $12$ parameters! To
simplify matters, we reduce the problem to a simpler 1-dimensional problem.

Consider the point $a$ where the extensions of the edges $e$ and $f$ meet, and
define $a^{\prime}$ analogously for $e^{\prime}$ and $f^{\prime}$ (see Figure
6(a)). If $a=a^{\prime}$ (implying that $e=e^{\prime}$ and $f=f^{\prime}$),
then it is easy to see that the bisector degenerates to a straight line
passing through $a$. Henceforth, let us assume that $a\neq a^{\prime}$.

Figure 6: Parameterizing a segment of the $(p,p^{\prime})$-bisector.

Because $z$ lies on the bisector, the cross ratio of $z$ and $p$ with respect
to its chord equals the cross ratio of $z^{\prime}$ and $p^{\prime}$ with
respect to its chord. Consider the line $\ell$ passing through $p$ and
$p^{\prime}$. Let $x$ and $y$ be the points lying on the intersection of
$\ell$ where the extension of the edge $e$ and $f$ intersects $\ell$,
respectively. Define $x^{\prime}$, and $y^{\prime}$ analogously for the edges
$e^{\prime}$ and $f^{\prime}$ (see Figure 6(b)). (The figure suggests that $p$
and $p^{\prime}$ lie between the pairs $(x,y)$ and $(x^{\prime},y^{\prime})$,
but this generally need not be the case. Irrespective of the order, the
projection preserves cross ratios and hence preserves Hilbert distances.) Let
$o$ be the point along $\ell$ such that
$(o,p;y,x)=(o,p^{\prime};y^{\prime},x^{\prime})$. By consideration of Hilbert
distances and the intermediate value theorem, it follows that such a point
exists within the line segment $pp^{\prime}$. Its uniqueness follows from
simple algebraic properties of cross ratios.

Now that all the points are on a common line, we can think of these quantities
as scalars. Define $\alpha$ and $\alpha^{\prime}$ such that $o+\alpha$ is the
point along $\ell$ where the line extending $za$ intersects $\ell$, and
$o+\alpha^{\prime}$ is the point where the line extending $za^{\prime}$
intersects $\ell$. By basic projective geometry and the fact that $z$ is on
the bisector, we have
$(o+\alpha,p;y,x)=(o+\alpha^{\prime},p^{\prime};y^{\prime},x^{\prime})$.
Observe that any point on the bisector can be described by a pair
$(\alpha,\alpha^{\prime})$, by computing the associated points on $\ell$,
shooting rays from $a$ and $a^{\prime}$ through these respective points, and
computing their intersection point. The following lemma shows that the
reciprocals of $\alpha$ and $\alpha^{\prime}$ have a simple linear
relationship. The proof is rather technical, and appears in the appendix.

lemmaLemSB Given a convex polygon $K\in\mathbb{R}^{2}$, sites
$p,p^{\prime}\in\operatorname{int}(K)$, and a segment of the
$(p,p^{\prime})$-bisector determined by edges $e$, $f$, $e^{\prime}$ and
$f^{\prime}$ as described above. For any point $z$ on the bisector, let
$o+\alpha$ and $o+\alpha^{\prime}$ denote the respective intersection points
of the lines $za$ and $za^{\prime}$ with the line $\ell$ through
$pp^{\prime}$. Then $1/\alpha$ and $1/\alpha^{\prime}$ are related by a linear
function depending on the above quantities.

This representation allows us to perform the essential operation needed by our
Voronoi diagram algorithms of tracing a bisector segment. We can use one of
the values $\alpha$ or $\alpha^{\prime}$ as the principal parameter of the
curve, and then use the linear relation to ascertain the value of the other
parameter. We can then solve for the events of consequence, such as the end of
the segment (when one of the chords through the bisector point encounters a
new edge of $K$) or the location of a Voronoi vertex, where two bisectors
meet.

##  4 Randomized Incremental Algorithm

In this section we present a randomized incremental algorithm to compute the
Hilbert Voronoi diagram for a set of $n$ sites contained in a $m$-sided convex
polygon $K$. Our algorithm follows the structure of other incremental
algorithms for Voronoi diagrams (see, e.g., [11, 13]), and has the added
benefit of generating a point-location data structure for the final diagram.
This data structure locates the closest site to a point $q\in K$ in expected
query time $O((\log n)(\log mn))$ (where the expectation is over the random
choices made in the construction).

The sites are randomly permuted, and then inserted one by one into the
diagram. The basis case is trivial, since the Voronoi cell of a single site is
the entire body. To facilitate point location, we augment the diagram through
the addition of line segment _spokes_ about each site. Recalling that each
Voronoi cell is star shaped, about each site we add line segments connecting
it to the boundary vertices of this cell, including its Voronoi vertices, the
joints between consecutive bisector segments along each Voronoi edge, and the
intersection of a Voronoi edge and the boundary of $K$, and the vertices of
$K$ that lie within the Voronoi cell. This produces a (topological)
triangulation of the diagram whose size is proportional to the size of the
diagram itself. It may be stored in any standard data structure for planar
subdivisions, like a doubly connected edge list [8].

Locating a point in the current diagram is performed through the use of a
_history DAG_ , that is, a directed acyclic graph whose terminal nodes
correspond to triangles in the current diagram. The structure encodes the
history of changes to the diagram. The addition of a new site will result in
the creation of a number of new triangles, and the destruction of old ones.
Each old triangle will store a reference to one of the new triangles that
replaced it (as described in greater detail below).

The insertion process works as follows. When a new site $p_{i}$ is inserted,
we first employ a search through the history DAG to determine the triangle of
the current diagram containing it (see Figure 7(a)). From this triangle, we
know the closest site in the current diagram, say $p_{j}$. We find the
midpoint (in the Hilbert sense) on the line segment between $p_{i}$ and
$p_{j}$. Starting at this point, we proceed to trace the boundary of the
Voronoi cell of $p_{i}$ in the new diagram in counterclockwise order about
$p_{i}$ (see Figure 7(b)). There are two cases that arise:

Bisector Trace:

We are tracing the bisector between $p_{i}$ and some existing site $p_{k}$
(see Figure 7(c)). We consider the sectors of $p_{i}$ and $p_{k}$ containing
the current portion of the $(p_{i},p_{k})$-bisector. By applying the
parameterization from Lemma 6, we can trace the bisector until (1) we
encounter the boundary of either sector, (2) we encounter the bisector between
$p_{k}$ and another site, or (3) we encounter the boundary of $K$.

In the first case, we create a new segment vertex here, add spokes to this
vertex, erase the extension of the sector edge (shown as a broken line in
Figure 7(c)) and continue the tracing in the new sector. In the second case,
we create a new Voronoi vertex, add spokes to this vertex from its three
defining sites, and continue the trace along the new bisector. In the third
case, we insert two spokes joining the point where the bisector encounters the
boundary to $p_{i}$ and $p_{k}$, respectively. We then transition to the
boundary trace described next.

Boundary Trace:

We are tracing the Voronoi cell of $p_{i}$ along $K$’s boundary. We walk along
the boundary of $K$ in counterclockwise order, considering each consecutive
sector of the closest site $p_{k}$, prior to $p_{i}$’s insertion. By applying
the parameterization from Lemma 6, we determine whether the
$(p_{i},p_{k})$-bisector intersects $K$’s boundary within the intersection of
the current pair of sectors. If so, we identify this point on the $\partial
K$, add spokes to each of $p_{i}$ and $p_{k}$, and then resume tracing along
the $(p_{i},p_{k})$-bisector. Otherwise, we encounter one of the two sector
boundaries, and we continue the tracing the next sector.

Along the way, we erase spokes from the current diagram, and/or introduce new
spokes connected to $p_{i}$. When we return to our starting point, the
insertion is completed.

Figure 7: Inserting a new site into the augmented diagram.

Point location in the history DAG is performed as follows for a query point
$q$. The root node is associated with the entire polygon $K$. Each time a
triangle is destroyed by the insertion of some point, we store a link to the
site whose insertion caused the destruction (the root points to the first site
inserted). We proceed as in Guibas, Knuth, and Sharir to determine the actual
triangle containing the point in $O(\log mn)$ time as follows [11]. Let
$p_{i}$ denote the inserted site that caused $q$’s triangle to change, and let
$p_{j}$ denote the site containing $q$ prior this event. Either $p_{j}$ is
still $q$’s closest site or it is changed to $p_{i}$. We first compare the
distance from $q$ to each of these sites. Once we have done this, we perform a
radial binary search around this site to determine the triangle containing
$q$. This radial search can be done in $O(\log mn)$ time. (As we shall see
below, while the expected number of structural changes per insertion is $O(1)$
in expectation, we cannot infer that this is the case for an arbitrary query
point. Also, we need to determine the triangle containing $q$ in order to
bound the number of length of the search path for $q$ in the history DAG.)
This completes the description of the algorithm. What remains is to analyze
the algorithm’s expected case running time.

######  Lemma 4.1.

Assuming that sites are inserted in random order, the expected number of
structural changes to the diagram over the course of the algorithm is $O(mn)$.

######  Proof 4.2.

We employ a standard backwards analysis. Consider the final diagram consisting
of $n$ sites. Because the sites have been inserted in random order, each site
is equally likely to have been the last to be inserted. By Lemma 3.5, the
average number of Voronoi edges on any Voronoi cell is $O(1)$ and the average
number of bisector segments on each Voronoi edge is $O(m)$.

The number of structural changes incurred by the insertion of a site is
proportional to its number of Voronoi edges in the final diagram times the
number of bisector segments on each of these edges (plus at most $m$ in case
the Voronoi cell contains portions of the boundary of $K$). Therefore, the
expected number of structural changes due the last insertion is $O(m)$. Since
this holds irrespective of $n$, it follows that the total number of structural
changes over all $n$ insertions is $O(mn)$.

Next, we consider expected time needed to perform point location.

######  Lemma 4.3.

Let $q$ be any fixed point of the plane. If the point-location structure is
constructed by inserting the sites in random order, then the expected cost of
searching to locate the radial triangle containing $q$ in the final Voronoi
diagram is $O((\log n)(\log mn))$.

######  Proof 4.4.

The triangle containing $q$ depends on at most four sites. (Each triangle
depends on the site $p_{1}$ where its two spokes meet. If the base of the
triangle is a bisector, it also depends on the site $p_{2}$ on the other side
of the bisector. Finally, either or both of remaining two vertices may be a
Voronoi vertices, between $p_{1}$, $p_{2}$, and two other sites $p_{3}$ and
$p_{4}$, respectively.) So, the probability that $q$ changes triangle
membership during $i$th insertion is at most $\frac{4}{i}$. The total number
of times $q$ descends to a new triangle in the history DAG in expectation is
$\sum_{i=1}^{n}\frac{4}{i}=O(\log n)$. Each time such a descent occurs, we
perform a radial search (described above) taking time $O(\log mn)$. Therefore,
the total expected search time is $O((\log n)(\log mn))$.

Combining the total expected update time and the expected search time for each
of the $n$ sites, we have:

######  Theorem 4.5.

Given an $m$-sided convex polygon $K$ in $\mathbb{R}^{2}$ and a set of $n$
sites $S$ in $K$, the randomized incremental algorithm computes
$\operatorname{Vor}_{K}(S)$ in expected time $O(nm+n(\log n)(\log mn))$ (where
the expectation is over all possible insertion orders).

##  5 Divide and Conquer Algorithm

In this section we present an algorithm for constructing the Hilbert Voronoi
diagram for a set of $n$ sites contained in a $m$-sided convex polygon $K$.
Our algorithm follows the structure of the standard divide and conquer
algorithm for the Euclidean Voronoi diagram (see, e.g., [18]).

The algorithm begins by partitioning the sites about a vertical line $\ell$
into two subsets, $S_{L}$ and $S_{R}$, of roughly equal sizes that lie to the
left and right of this line, respectively. We recursively compute the Hilbert
Voronoi diagrams $\operatorname{Vor}_{K}(S_{L})$ and
$\operatorname{Vor}_{K}(S_{R})$ (see Figure 8(b) and (c)). To merge them, we
compute the bisector between $S_{L}$ and $S_{R}$, which we denote by
$B(S_{L},S_{R})$. This consists of those points that are equidistant (in the
Hilbert sense) from their closest sites in $S_{L}$ and $S_{R}$. We shall see
below that this consists of a collection of curves, called _components_ , each
being the concatenation of Voronoi edges between two sites, one in $S_{L}$ and
one in $S_{R}$ (see Figure 8(d)). Each component terminates on the boundary
$K$ (that is, no component is a closed loop). We will show below that it is
possible to construct all the components of $B(S_{L},S_{R})$ by a single
bottom-up traversal, which runs in $O(mn)$ time. Once the bisector is
constructed, we complete the merging process, by discarding the portions of
$\operatorname{Vor}_{K}(S_{L})$ that lie on the right side of the bisector and
the portions of $\operatorname{Vor}_{K}(S_{R})$ that lie on the left side of
bisector. Before describing the bisector-construction process, we explain the
bisector’s structure.

Figure 8: Divide-and-conquer algorithm, bisectors, and the proof of Lemma
5.1(iii).

######  Lemma 5.1.

Given two sets of sites $S_{L}$ and $S_{R}$ separated by a vertical line
$\ell$, the Hilbert bisector $B(S_{L},S_{R})$ consists of a collection of
pairwise disjoint curves, called _components_ , where:

  1. $(i)$

Each component is the concatenation of Voronoi edges from the final diagram,
each between a site in $S_{L}$ and another in $S_{R}$.

  2. $(ii)$

Every point on $B(S_{L},S_{R})$ is visible to some point on $\ell\cap K$, that
is, for each $x\in B(S_{L},S_{R})$ there exists a point $y\in\ell\cap K$ such
that the open line segment $xy$ does not intersect $B(S_{L},S_{R})$.

  3. $(iii)$

Each component is terminated by endpoints that lie on the boundary of $K$ (and
hence no component is a closed loop).

  4. $(iv)$

There are at most $n$ components, and the total combinatorial complexity of
$B(S_{L},S_{R})$ is $O(mn)$.

######  Proof 5.2.

Claim (i) follows from basic facts about Voronoi diagrams. Every point $q\in
B(S_{L},S_{R})$ is on the Voronoi cell of at least two sites, one on each side
of $\ell$. By Lemma 3.1, the line segment from $q$ to each site lies entirely
within the Voronoi cell, and hence does not intersect $B(S_{L},S_{R})$. One of
these two lines must cross $\ell\cap K$, which establishes (ii).

To prove (iii), suppose to the contrary that a component does not contact
$K$’s boundary, implying that it forms a closed loop. Let $q$ be the point of
this loop that is farthest from $\ell$ (that is, has the largest
$x$-coordinate). By claim (ii) and consideration points infinitesimally close
on either side of $q$ on the loop, $q$ must be visible to two sites
$p,p^{\prime}\in S_{L}$ such that the segment $qp$ passes above the loop and
$qp^{\prime}$ passes below the loop (see Figure 8(e)). Therefore, $q$ is a
Voronoi vertex between $p$, $p^{\prime}$, and the closest site
$p^{\prime\prime}$ in $S_{R}$. Thus, $q$ is the center of a Hilbert ball
passing through these three sites. However, because the line segment
$pp^{\prime}$ lies entirely to the left of $\ell$ and $p^{\prime\prime}$ lies
between these points to the right of $\ell$, this violates the convexity of
Hilbert balls, a contradiction.

Claim (iv) follows from the fact that each component contains at least one
full Voronoi edge from the final diagram, and by Lemma 3.5 there are at most
$O(n)$ Voronoi edges in the final diagram. Also, the bisector is part of the
final diagram, and hence its total complexity cannot exceed that of the final
diagram, which by Lemma 3.5 is $O(mn)$.

Let us consider how the bisector $B(S_{L},S_{R})$ is constructed. As in the
previous section, we will triangulate each Voronoi cell by adding _spokes_ ,
that is, line segments between each site and the various vertices (Voronoi
vertices, bisector segment endpoints, vertices of $K$) that lie on the
boundary of its Voronoi cell (see Figure 9(a)). As mentioned above, we
construct the bisector from bottom to top. (Note, however, that the components
of $B(S_{L},S_{R})$ need not be vertically monotone.) We start at the lowest
endpoint of $q$ of $\ell\cap K$. Let $p$ and $p^{\prime}$ be the sites of
$S_{L}$ and $S_{R}$ that are closest to $q$, respectively. We may assume that
the construction algorithms for $\operatorname{Vor}_{K}(S_{L})$ and
$\operatorname{Vor}_{K}(S_{R})$ provide us with the identities of $p$ and
$p^{\prime}$ as well as the triangles of their respective Voronoi cells that
contain $q$. In $O(1)$ time, we can determine the closer of $p$ or
$p^{\prime}$ to $q$. If it is $p$, we begin a boundary trace counterclockwise
about $\partial K$ and if it is $p^{\prime}$, we begin a boundary trace
clockwise about $\partial K$. These boundary traces are described below.

Figure 9: Tracing $B(S_{L},S_{R})$. (Drawing is not geometrically accurate.)

Generally there are two types tracings that we need to perform, depending on
whether we are tracing a component of $B(S_{L},S_{R})$ or walking along $K$’s
boundary in search of the next component. These are similar to the tracings we
described in the case of the randomized algorithm. Note that generally, we are
tracing counterclockwise about the sites of $S_{L}$ and clockwise about the
sites of $S_{R}$ (see Fig. 9).

Bisector Trace:

We are tracing the bisector between two sites $p_{i}\in S_{L}$ and $p_{k}\in
S_{R}$ (see Figure 7(c)). We consider the sectors of $p_{i}$ and $p_{k}$
containing the current portion of the $(p_{i},p_{k})$-bisector. As in the
bisector tracing for the randomized algorithm, we employ Lemma 6 to trace the
bisector until either (1) it intersects one of the two sector edges, (2) hits
another bisector, or (3) hits $K$’s boundary.

In the first case, we erase the extension of the sector edge (shown as a
broken line in Figure 9(d)), create a new segment vertex here, add spokes to
this vertex, and continue the tracing in the new sector. In the second case,
we create a new Voronoi vertex, add spokes to this vertex from its three
defining sites, and continue the trace along the appropriate bisector (always
walking on a bisector between a left-side site and a right-side site). In the
third case, we insert two spokes joining the point where the bisector
encounters the boundary to $p_{i}$ and $p_{k}$, respectively. We then
transition to the boundary trace described next.

Boundary Trace:

There are two cases, depending on whether we are tracing along the boundary of
a cell of $S_{L}$ or $S_{R}$. In the former case, we walk counterclockwise
along $K$’s boundary until reaching the end of the current sector, and in the
latter we walk clockwise. We consider each consecutive sector of the closest
sites $p_{i}$ from $S_{L}$ and $p_{j}$ from $S_{R}$. By applying the
parameterization from Lemma 6, we determine whether the
$(p_{i},p_{k})$-bisector intersects $K$’s boundary within the intersection of
the current pair of sectors. If so, we identify this point on the $\partial
K$, add spokes to each of $p_{i}$ and $p_{k}$, and then resume tracing along
the $(p_{i},p_{k})$-bisector (see Figure 9(b)–(d)). Otherwise, we encounter
one of the two sector boundaries, and we continue the tracing along the
boundary.

The tracing process runs in $O(1)$ time for each newly added segment to the
bisector, for a total of $O(mn)$ time. The overhead for the divide-and-conquer
is dominated by the tracing time, which implies that divide-and-conquer
algorithm’s overall running time satisfies the recurrence $T(n)=2T(n/2)+mn$.
This solves to $O(nm\log n)$. In summary, we obtain the following result.

######  Theorem 5.3.

Given an $m$-sided convex polygon $K$ in $\mathbb{R}^{2}$ and a set of $n$
sites $S$ in $K$, the divide-and-conquer algorithm computes
$\operatorname{Vor}_{K}(S)$ in time $O(nm\log n)$.

##  Appendix A Appendix

*

######  Proof A.1.

To simplify notation, let $\underline{xy}$ be a shorthand for $x-y$. Given
that $(o+\alpha,p;x,y)=(o+\alpha^{\prime},p^{\prime};x^{\prime},y^{\prime})$,
we have

$\frac{\underline{x(o+\alpha)}\cdot\underline{py}}{\underline{xp}\cdot\underline{(o+\alpha)y}}~{}=~{}\frac{\underline{x^{\prime}(o+\alpha^{\prime})}\cdot\underline{p^{\prime}y^{\prime}}}{\underline{x^{\prime}p^{\prime}}\cdot\underline{(o+\alpha^{\prime})y^{\prime}}}.$

Observe that $\underline{(x+y)z}=x+y-z=\underline{xz}+y$ and
$\underline{z(x+y)}=z-x-y=\underline{zx}-y$. Expanding both sides, yields

$\displaystyle\left(\underline{x(o+\alpha)}\cdot\underline{py}\right)\left(\underline{x^{\prime}p^{\prime}}\cdot\underline{(o+\alpha^{\prime})y^{\prime}}\right)~{}=~{}\left(\underline{x^{\prime}(o+\alpha^{\prime})}\cdot\underline{p^{\prime}y^{\prime}}\right)\left(\underline{xp}\cdot\underline{(o+\alpha)y}\right)$
$\displaystyle\left((\underline{xo}-\alpha)\cdot\underline{py}\right)\left(\underline{x^{\prime}p^{\prime}}\cdot(\underline{oy^{\prime}}+\alpha^{\prime})\right)~{}=~{}\left((\underline{x^{\prime}o}-\alpha^{\prime})\cdot\underline{p^{\prime}y^{\prime}}\right)\left(\underline{xp}\cdot(\underline{oy}+\alpha)\right)$
$\displaystyle\big{(}\underline{xo}\cdot\underline{py}-\alpha\cdot\underline{py}\big{)}\big{(}\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}+\underline{x^{\prime}p^{\prime}}\cdot\alpha^{\prime}\big{)}~{}=~{}\big{(}\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}-\alpha^{\prime}\cdot\underline{p^{\prime}y^{\prime}}\big{)}\big{(}\underline{xp}\cdot\underline{oy}+\underline{xp}\cdot\alpha\big{)}$
$\displaystyle\underline{xo}\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}-\alpha\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}+\underline{xo}\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\alpha^{\prime}-\alpha\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\alpha^{\prime}$
$\displaystyle~{}=~{}\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\underline{oy}-\alpha^{\prime}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\underline{oy}+\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\alpha-\alpha^{\prime}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\alpha$

Collecting common factors of $\alpha$ and $\alpha^{\prime}$, we have

$\displaystyle\left(\underline{xo}\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}-\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\underline{oy}\right)-\left(\underline{py}\cdot\underline{x^{\prime}p^{\prime}}-\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\right)\alpha\alpha^{\prime}$
$\displaystyle~{}=~{}\left(\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}+\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\right)\alpha-\left(\underline{xo}\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}+\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\underline{oy}\right)\alpha^{\prime}.$
(1)

By definition of $o$, we have

$\frac{\underline{xo}\cdot\underline{py}}{\underline{xp}\cdot\underline{oy}}~{}=~{}\frac{\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}}{\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}}\quad\Longrightarrow\quad\underline{xo}\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}-\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\underline{oy}~{}=~{}0.$

Thus, the first term in Eq.(A.1) vanishes, which yields

$\left(\underline{py}\cdot\underline{x^{\prime}p^{\prime}}-\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\right)\alpha\alpha^{\prime}~{}=~{}\left(\underline{xo}\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}+\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\underline{oy}\right)\alpha^{\prime}-\left(\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}+\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\right)\alpha.$

Letting:

$\displaystyle A$
$\displaystyle~{}=~{}\underline{py}\cdot\underline{x^{\prime}p^{\prime}}-\underline{p^{\prime}y^{\prime}}\cdot\underline{xp},\quad
B~{}=~{}\underline{xo}\cdot\underline{py}\cdot\underline{x^{\prime}p^{\prime}}+\underline{p^{\prime}y^{\prime}}\cdot\underline{xp}\cdot\underline{oy},\quad\mathrm{and}$
$\displaystyle C$
$\displaystyle~{}=~{}\underline{py}\cdot\underline{x^{\prime}p^{\prime}}\cdot\underline{oy^{\prime}}+\underline{x^{\prime}o}\cdot\underline{p^{\prime}y^{\prime}}\cdot\underline{xp},$

and dividing by $\alpha\alpha^{\prime}$, we see that the bisector is given by
the following linear relation in $1/\alpha$ and $1/\alpha^{\prime}$

$A~{}=~{}\frac{B}{\alpha}-\frac{C}{\alpha^{\prime}},$

as desired.

## References

  * [1] Ahmed Abdelkader, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount.  Approximate nearest neighbor searching with non-euclidean and weighted distances.  In Proc. 30th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 355–372, 2019.  https://doi.org/10.1137/1.9781611975482.23 doi:10.1137/1.9781611975482.23.
  * [2] Ahmed Abdelkader and David M. Mount.  Economical Delone sets for approximating convex bodies.  In Proc. 16th Scand. Workshop Algorithm Theory, pages 4:1–4:12, 2018.
  * [3] Rahul Arya, Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount.  Optimal bound on the combinatorial complexity of approximating polytopes.  In Proc. 31st Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 786–805, 2020.  URL: https://arxiv.org/abs/1910.14459, https://doi.org/10.1137/1.9781611975994.48 doi:10.1137/1.9781611975994.48.
  * [4] Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount.  Near-optimal $\varepsilon$-kernel construction and related problems.  In Proc. 33rd Internat. Sympos. Comput. Geom., pages 10:1–15, 2017.  URL: https://arxiv.org/abs/1604.01175.
  * [5] Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount.  On the combinatorial complexity of approximating polytopes.  Discrete Comput. Geom., 58(4):849–870, 2017.  https://doi.org/10.1007/s00454-016-9856-5 doi:10.1007/s00454-016-9856-5.
  * [6] Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount.  Optimal approximate polytope membership.  In Proc. 28th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 270–288, 2017.
  * [7] Herbert Busemann.  The Geometry of Geodesics.  Academic Press, 1955.
  * [8] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.  Computational Geometry: Algorithms and Applications.  Springer, 3rd edition, 2010.
  * [9] Friedrich Eisenbrand, Nicolai Hähnle, and Martin Niemeier.  Covering cubes and the closest vector problem.  In Proc. 27th Annu. Sympos. Comput. Geom., pages 417–423, 2011\.
  * [10] Friedrich Eisenbrand and Moritz Venzin.  Approximate CVPs in time $2^{0.802n}$.  Journal of Computer and System Sciences, 2021.
  * [11] Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir.  Randomized incremental construction of Delaunay and Voronoi diagrams.  Algorithmica, 7:381–413, 1992.  https://doi.org/10.1007/BF01758770 doi:10.1007/BF01758770.
  * [12] D. Hilbert.  Ueber die gerade linie als kürzeste verbindung zweier punkte.  Mathematische Annalen, 46:91–96, 1895.
  * [13] Rolf Klein, Kurt Mehlhorn, and Stefan Meiser.  Randomized incremental construction of abstract Voronoi diagrams.  Comput. Geom. Theory Appl., 3(3):157–184, 1993.  URL: https://www.sciencedirect.com/science/article/pii/0925772193900333, https://doi.org/https://doi.org/10.1016/0925-7721(93)90033-3 doi:https://doi.org/10.1016/0925-7721(93)90033-3.
  * [14] Márton Naszódi and Moritz Venzin.  Covering convex bodies and the closest vector problem.  arXiv preprint arXiv:1908.08384, 2019.
  * [15] Frank Nielsen and Laetitia Shao.  On balls in a Hilbert polygonal geometry (multimedia contribution).  In Proc. 33rd Internat. Sympos. Comput. Geom., volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1–67:4. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017.  URL: http://drops.dagstuhl.de/opus/volltexte/2017/7244, https://doi.org/10.4230/LIPIcs.SoCG.2017.67 doi:10.4230/LIPIcs.SoCG.2017.67.
  * [16] Athanase Papadopoulos and Marc Troyanov.  From Funk to Hilbert geometry.  In Handbook of Hilbert geometry, volume 22 of IRMA Lectures in Mathematics and Theoretical Physics, pages 33–68. European Mathematical Society Publishing House, 2014.  URL: https://hal.archives-ouvertes.fr/hal-01015584, https://doi.org/10.4171/147-1/2 doi:10.4171/147-1/2.
  * [17] Athanase Papadopoulos and Marc Troyanov.  Handbook of Hilbert geometry, volume 22 of IRMA Lectures in Mathematics and Theoretical Physics.  European Mathematical Society Publishing House, 2014.
  * [18] Franco P. Preparata and Michael Ian Shamos.  Computational Geometry: An Introduction.  Springer, 1985.
  * [19] Thomas Rothvoss and Moritz Venzin.  Approximate CVP in time $2^{0.802n}$ – now in any norm!  arXiv preprint arXiv:2110.02387, 2021.
  * [20] Marc Troyanov.  Funk and Hilbert geometries from the Finslerian viewpoint.  In Handbook of Hilbert geometry, volume 22 of IRMA Lectures in Mathematics and Theoretical Physics, pages 69–110. European Mathematical Society Publishing House, 2014.  URL: https://hal.archives-ouvertes.fr/hal-01015584, https://doi.org/10.4171/147-1/2 doi:10.4171/147-1/2.
  * [21] Sumio Yamada.  Convex bodies in Euclidean and Weil-Petersson geometries.  Proc. Amer. Math. Soc., 142(2):603–616, 2014.  https://doi.org/10.1090/S0002-9939-2013-11841-1 doi:10.1090/S0002-9939-2013-11841-1.