Farthest-Point Voronoi Diagrams in the Hilbert Metric

We denote by $\text{FV}(S)$ the farthest-point Voronoi diagram of $n$ point sites in the Hilbert metric defined by a convex $m$-gon $\mathrm{\Omega }$. Unlike Voronoi diagrams in the Euclidean metric, $\text{FV}(S)$ poses a few difficulties in the computation. The Hilbert distance between points is defined as the logarithm of the cross-ratio of them and the intersections of the line through the points with the domain boundary. It takes $O(\log m)$ time to compute the distance between points. The bisector between any two sites is a piecewise conic curve consisting of $O(m)$ segments. Thus, a naïve divide-and-conquer algorithm using bisectors may take $\mathrm{\Omega }(\min \{nm,m^2\})$ time.

We show that $\text{FV}(S)$ has combinatorial complexity $\mathrm{\Theta }(m)$, which is independent of the number of sites. Moreover, we present an $O(n(\log n+{\log }^{2}m)+m\log n)$-time algorithm for computing the diagram. This is the first algorithm for computing $\text{FV}(S)$.

In Section 2, we introduce the Hilbert metric, Hilbert balls, Hilbert bisectors, and $\text{FV}(S)$. In the Euclidean metric, a site of $S$ has a nonempty cell in the farthest-point Voronoi diagram if and only if it is a vertex of the convex hull of $S$ [11]. This is, however, not always the case in the Hilbert metric. If a site has a nonempty cell in $\text{FV}(S)$, it is a vertex of the convex hull. But not every vertex of the convex hull always has a nonempty cell in $\text{FV}(S)$. In Section 3, we characterize this phenomenon and show that each cell in $\text{FV}(S)$ is connected and incident to the boundary of $\mathrm{\Omega }$. We give an ordering lemma for the sites of $S$ and their Voronoi cells appearing along the boundary of $\mathrm{\Omega }$.

In Section 4, we analyze the combinatorial complexity of $\text{FV}(S)$. We show that $\text{FV}(S)$ has $O(m)$ edges and each Voronoi cell is connected. Using this, we show that the number of sites with nonempty cells is $O(m)$. By Euler’s formula, we show that $\text{FV}(S)$ has $O(m)$ vertices. We conclude that the combinatorial complexity of $\text{FV}(S)$ is $O(m)$. Additionally, since the complexity of $\text{FV}(S)$ is at least the complexity of $\mathrm{\Omega }$, a lower bound on the combinatorial complexity of $\text{FV}(S)$ is $\mathrm{\Omega }(m)$. As a result, we give a tight upper bound on the combinatorial complexity of $\text{FV}(S)$, which is $\mathrm{\Theta }(m)$ and independent of the number of the sites of $S$.

In Section 5, we give an efficient algorithm of $O(n(\log n+{\log }^{2}m)+m\log n)$ time for computing $\text{FV}(S)$. Our algorithm consists of three stages. The subsections in Section 5 describe these stages of the algorithm. In the first stage, we compute the convex hull of $S$ and remove the points contained in the interior of the convex hull of $S$. In the second stage, we construct $\text{FV}(S)$ restricted to the boundary of $\mathrm{\Omega }$ incrementally by adding the sites of $S$ one by one in clockwise orientation along the convex hull of $S$. In doing so, we maintain a list $ℒ$ of sites that have nonempty boundary cell. Initially, $ℒ$ contains the first two consecutive sites of $S$. When the next site $s$ is added, we check whether $s$ is the farthest from an intersection point of the boundary cells corresponding to the first and the last sites stored in $ℒ$. If $s$ is not the farthest one from the point, it has an empty cell so we are done and move on to the next iteration. If $s$ is the farthest one, it has a nonempty cell so we append $s$ to $ℒ$. We compute the boundary cell of $s$ along the boundary of $\mathrm{\Omega }$ from the intersection point. In this way, we compute all sites of $S$ whose Voronoi cell is nonempty in $O(n(\log n+{\log }^{2}m))$ time.

In the third stage, we construct $\text{FV}(S)$ by subdividing $\mathrm{\Omega }$ into Voronoi cells using $\text{FV}(S)$ restricted to the boundary of $\mathrm{\Omega }$. Our algorithm uses a divide-and-conquer technique similar to the one by Shamos and Hoey [24] that computes the nearest-site Voronoi diagram in the plane under the Euclidean metric. Roughly speaking, we partition a site sequence into two subsequences, $S_L$ and $S_R$, of roughly equal size, and compute $\text{FV}(S_L\cup S_R)$ by merging $\text{FV}(S_L)$ and $\text{FV}(S_R)$ along their bisector recursively. But the merge step requires a novel algorithmic idea and an in-depth analysis as each bisector is a piecewise conic curve consisting of $O(m)$ segments. In each recursive step, we compute approximate bisectors such that they become the exact bisectors in the last recursive depth. We show that this can be done in $O(m\log \min \{m,n\})$ time in total. Therefore, $\text{FV}(S)$ can be computed in $O(n(\log n+{\log }^{2}m)+m\log n)$ time in total.

The quantity in the logarithm is the cross-ratio of $(p,q;\overline{q},\overline{p})$. If $p$ or $q$ lies on $\partial \mathrm{\Omega }$, $d(p,q)$ can be formally defined to be $+\mathrm{\infty }$. This corresponds to a limiting case that a denominator approaches zero. The Hilbert distance $d$ is extended to all pairs of points by letting $d(p,p)=0$. It satisfies the axioms of a metric, and in particular, it is symmetric and the triangle inequality holds. Observe $d(p,q)+d(q,r)=d(p,r)$ if $p,q$, and $r$ are collinear in $\mathrm{\Omega }$ [21].

In the remainder of the paper, we abuse the notation and use $\mathrm{\Omega }$ to denote a convex polygon with $m$ vertices in the plane. For any two points $p,q\in \text{int}(\mathrm{\Omega })$, a simple binary search makes it possible to determine the two edges of $\partial \mathrm{\Omega }$, each containing an endpoint of $\chi (p,q)$. Thus, the Hilbert distance between two points can be computed in $O(\log m)$ time.

For a point $p\in \text{int}(\mathrm{\Omega })$ and $\rho >0$, let $B_{\mathrm{\Omega }}(p,\rho )$ denote the Hilbert ball of radius $\rho$ centered at $p$. Nielsen and Shao characterized the shape of Hilbert balls and showed how to compute them [20]. Consider the set of $\chi (p,v)$’s for vertices $v$ of $\mathrm{\Omega }$, which we call the spokes of $p$. See Figure 1(a). For each $\chi (p,v)$, there are exactly two points lying on $\chi (p,v)$ whose Hilbert distance from $p$ is $\rho$. Those points are all in convex position. Then $B_{\mathrm{\Omega }}(p,\rho )$ is the convex polygon with vertices on those $2m$ points. We say $B_{\mathrm{\Omega }}(p,\rho )$ is the Hilbert ball centered at $p$ with radius $\rho$. For a point $x\in B_{\mathrm{\Omega }}(p,\rho )$, $d(p,x)\le \rho$; the equality holds for $x$ lying on the boundary of $B_{\mathrm{\Omega }}(p,\rho )$. For a point $x\in \mathrm{\Omega }\setminus B_{\mathrm{\Omega }}(p,\rho )$, $d(p,x)>\rho$. See Figure 1(b).

We extend the concept of Hilbert balls to ones centered at points in $\partial \mathrm{\Omega }$, which we call infinite Hilbert balls. Let $p$ be a point in $\partial \mathrm{\Omega }$, and let $q$ be a point in $\text{int}(\mathrm{\Omega })$. For arbitrarily small $\delta >0$, let $p_{\delta }$ be the point on $pq$ with $|p{p}_{\delta }|=\delta$. As $\delta$ approaches 0, any sequence of Hilbert balls in the family $\{B_{\mathrm{\Omega }}(p_{\delta },d(p_{\delta },q))\}$ converges to the infinite Hilbert ball centered at $p$ with radius $d(p_{\delta },q)=d(p,q)$, which we denote by $B_{\mathrm{\infty }}(p,q)$. See Figure 1(c).

Gezalyan and Mount [15] introduced the Hilbert bisector of two points $p,q\in \text{int}(\mathrm{\Omega })$, denoted by $\gamma (p,q)$, which is the set of points $x\in \mathrm{\Omega }$ satisfying $d(x,p)=d(x,q)$. For any point $x\in \gamma (p,q)\cap \text{int}(\mathrm{\Omega })$, $q\in \partial B_{\mathrm{\Omega }}(x,d(x,p))$ and $p\in \partial B_{\mathrm{\Omega }}(x,d(x,q))$. For any point $x\in \gamma (p,q)\cap \partial \mathrm{\Omega }$, $q\in \partial B_{\mathrm{\infty }}(x,p)$ and $p\in \partial B_{\mathrm{\infty }}(x,q)$. For a point $x\in \mathrm{\Omega }$, let $p_1,p_2$ be two endpoints of $\chi (x,p)$, and let $q_1,q_2$ be two endpoints of $\chi (x,q)$. Let ${\mathrm{\ell }}_1$, $\mathrm{\ell }$, and ${\mathrm{\ell }}_2$ be the lines containing the segments $p_1{q}_1$, $pq$, and $p_2{q}_2$, respectively. If $x\in \partial \mathrm{\Omega }$, let $x=p_2=q_2$ and let ${\mathrm{\ell }}_2$ be the line tangent to $\mathrm{\Omega }$ at $x$. It is shown that two cross ratios, $(x,p;p_1,p_2)$ and $(x,q;q_1,q_2)$, are the same if and only if these three lines meet at a common point. It follows $d(x,p)=d(x,q)$, and thus $x$ is on the bisector. See Figure 2(a-b).

The Hilbert distances $d(p,x)$ and $d(q,x)$ of a point $x\in \text{int}(\mathrm{\Omega })$ are determined by the boundary edges of $\mathrm{\Omega }$ incident to $\chi (p,x)$ and $\chi (q,x)$, respectively. Consider the subdivision of $\mathrm{\Omega }$ by all spokes of $p$ and all spokes of $q$. Observe that for every point $x$ in a subregion, the set of edges of $\partial \mathrm{\Omega }$ incident to $\chi (p,x)$ and $\chi (q,x)$ remains the same. Thus, $d(p,x)$ and $d(q,x)$ for points $x$ in a subregion can be formulated in explicit functions, and thus we can obtain the Hilbert bisector of $p$ and $q$ restricted to the subregion from the functions. It has been shown that $\gamma (p,q)$ in a subregion is a conic curve. It follows that $\gamma (p,q)$ is a piecewise conic curve whose joints lie on subregion boundaries [9]. Thus, we say that $\gamma (p,q)$ consists of bisector segments. See Figure 2(c).

Lemma 2 naturally extends for infinite Hilbert balls. The lemma implies that $\gamma (p,q)\cap \gamma (q,r)$ is at most one point for any three points $p,q,r\in \text{int}(\mathrm{\Omega })$ not lying on the same line.

Let $S$ be a set of $n$ points lying in $\text{int}(\mathrm{\Omega })$ which we call sites. The farthest-point Voronoi diagram of $S$ in the Hilbert distance on $\mathrm{\Omega }$, denoted by $\text{FV}(S)$, is a subdivision of $\mathrm{\Omega }$ into cells in which the same point of $S$ is the farthest point in the Hilbert distance. The farthest-point Voronoi cell of a site $s\in S$, denoted by $V(s)$, is the set of points whose farthest site is $s$ in the Hilbert distance. Consider a point $p\in \mathrm{\Omega }$ contained in $V(s)$. If $p\in \text{int}(\mathrm{\Omega })$, $d(p,s)\ge d(p,s^{\prime })$ for all sites $s^{\prime }\in S$. If $p\in \partial \mathrm{\Omega }$, there is a point sequence ${\{q_i\}}_{i\in \mathbb{N}}$ contained in $\text{int}(\mathrm{\Omega })$ such that the sequence converges to $p$ and $d(q_i,s)\ge d(q_i,s^{\prime })$ for all sites $s^{\prime }\in S$ and for all $i\in \mathbb{N}$. Not every point of $S$ has a nonempty cell in $\text{FV}(S)$. We will investigate this in Section 3.

To find all valid sites of $S$ for $\text{FV}(S)$ and compute $\text{FV}(S)$ efficiently, we compute $\text{FV}(S)$ restricted to the boundary of $\mathrm{\Omega }$. We denote it by $\text{bFV}(S)$. The Voronoi cell in $\text{bFV}(S)$ of a site $s\in S$, denoted by $\beta (s)$, is the intersection of $V(s)$ and $\partial \mathrm{\Omega }$. We call a site $s\in S$ valid for $\text{bFV}(S)$ if $\beta (s)\ne \mathrm{\varnothing }$.

Gezalyan and Mount [15] showed that the combinatorial complexity of the nearest-point Voronoi diagram is $O(mn)$. We show that the combinatorial complexity of the farthest-point Voronoi diagram is $O(m)$. Recall that every bisector is a piecewise conic with joints lying on spokes. To analyze the combinatorial complexity of $\text{FV}(S)$, we count the number of Voronoi vertices and the total number of bisector segments in $\text{FV}(S)$. Let $\kappa (p)$ denote the set of farthest sites for a point $p$ in $\partial \mathrm{\Omega }$. If $\kappa (p)$ consists of a single element, we use $\kappa (p)$ to denote the element. The following lemma shows an upper bound on the number of bisector segments.

By Lemma 4, every site of $S$ contained in $\text{int}(\text{conv}(S))$ is not valid for $\text{FV}(S)$. Hence, we compute $\text{conv}(S)$ and remove all sites contained in its interior from $S$. This can be done in $O(n\log n)$ time. Thus, all remaining sites in $S$ are in convex position. We relabel them such that $⟨s_1,s_2\mathrm{\dots },s_n⟩$ is the sequence of sites in clockwise orientation along their convex hull.

Some sites of $S$, however, may not be valid for $\text{FV}(S)$. We will identify all valid sites of $S$ by computing $\text{bFV}(S)$. We do this incrementally by inserting sites one by one in order, checking if the newly inserted one is valid for the Voronoi diagram of the sites inserted so far, and handling the cases accordingly. We maintain a few structures. Let $S_i$ be the subset of $S$ consisting of the first $i$ sites of $S$ for $i=2,\mathrm{\dots },n$. Let ${\beta }_i(s)$ denote the Voronoi cell of $s\in S_i$ in $\text{bFV}(S_i)$. Let ${ℒ}_i$ be the list that maintains all valid sites for $\text{FV}(S_i)$.

Initially, let $S_2=\{s_1,s_2\}$ and ${ℒ}_2=[s_1,s_2]$. We compute $\text{bFV}(S_2)$ by computing the endpoints of $\gamma (s_1,s_2)$. In the $i$-th iteration with $i\ge 3$, we compute $\text{bFV}(S_i)$ and maintain ${ℒ}_i$ as follows. Let $s_l$ and $s_r$ be the first element and the last element in ${ℒ}_{i-1}$, respectively. Then there is a point $p$ shared by ${\beta }_{i-1}(s_l)$ and ${\beta }_{i-1}(s_r)$. By Lemma 8, $s_i$ is valid if and only if $p\in {\beta }_i(s_i)$. If , $s_i$ is not valid for $\text{FV}(S_i)$, and thus it is not valid for $\text{FV}(S)$. We set ${ℒ}_i={ℒ}_{i-1}$ and move on to the next iteration. If $d(s_i,p)\ge d(s_l,p)$, $s_i$ is valid for $\text{FV}(S_i)$. We set ${ℒ}_i={ℒ}_{i-1}$. Then we update $\text{bFV}(S_i)$ from $\text{bFV}(S_{i-1})$ by computing the endpoints of ${\beta }_i(s_i)$. This can be done by searching them along the boundary of $\mathrm{\Omega }$ from $p$, once in clockwise orientation and once in counterclockwise orientation. In doing so, we update ${ℒ}_i$ accordingly, and then append $s_i$ to ${ℒ}_i$.

Consider the case that we search for an endpoint of ${\beta }_i(s_i)$ along the boundary of $\mathrm{\Omega }$ in counterclockwise orientation from $p$. Let $q$ be the endpoint of ${\beta }_{i-1}(s_r)$ other than $p$. Observe that $q\in {\beta }_{i-1}(s_{r^{\prime }})$ for site $s_{r^{\prime }}$ previous to $s_r$ in ${ℒ}_{i-1}$. If , one endpoint of ${\beta }_i(s_i)$ lies on ${\beta }_{i-1}(s_r)$. We compute the endpoint of $\gamma (s_r,s_i)$ on ${\beta }_{i-1}(s_r)$. Otherwise, $s_r$ is not valid for $\text{FV}(S_i)$, and thus it is not valid for $\text{FV}(S)$. We remove $s_r$ from ${ℒ}_i$ and move on to $s_{r^{\prime }}$. We repeat this until one endpoint of ${\beta }_i(s_i)$ is found. See Figure 5.

We find the other endpoint of ${\beta }_i(s_i)$ in clockwise orientation similarly. After computing both endpoints of ${\beta }_i(s_i)$, we append $s_i$ to ${ℒ}_i$.

We can compute $d(s_i,p)$ and $d(s_l,p)$ in $O(\log m)$ time. If , we are done. If $d(s_i,p)\ge d(s_l,p)$, we identify all sites not valid for $\text{FV}(S_i)$ among sites valid for $\text{FV}(S_{i-1})$, and remove them from ${ℒ}_i$. This takes $O(n\log m)$ time in total over all insertion steps. Then we compute the endpoints of ${\beta }_i(s_i)$. Observe that one endpoint of ${\beta }_i(s_i)$ is an endpoint of $\gamma (s_i,s)$ and the other endpoint of ${\beta }_i(s_i)$ is an endpoint of $\gamma (s_i,s^{\prime })$, where $s$ and $s^{\prime }$ are the first and the last elements in ${ℒ}_i$. We can compute the endpoints of ${\beta }_i(s_i)$ in $O({\log }^{2}m)$ time by Lemma 13. Since the number of sites is $n$, it takes $O(n{\log }^{2}m)$ time in total to compute $\text{bFV}(S)$.

We have preprocessed $\text{bFV}(S)$ of size $O(m)$ and all $O(\min \{m,n\})$ sites valid for $\text{FV}(S)$ and $\text{bFV}(S)$ by Lemma 14. We give an algorithm for computing $\text{FV}(S)$ in $O(\min \{m\log m,m\log n\})$ time by subdividing $\mathrm{\Omega }$ into Voronoi cells using $\text{bFV}(S)$. Our algorithm is based on a divide-and-conquer technique similar to the one by Shamos and Hoey [24] that computes the nearest-site Voronoi diagram in the plane under the Euclidean metric. But the merge step requires a novel algorithmic idea and an in-depth analysis to reduce the running time as each bisector is a piecewise conic curve consisting of $O(m)$ segments.

Let $\widehat{S}=⟨s_0,\mathrm{\dots },s_{t-1}⟩$ denote the sequence of sites valid for $\text{FV}(S)$ such that $s_0,\mathrm{\dots },s_{t-1}$ appear in clockwise orientation along $\text{conv}(\widehat{S})$. Observe $t=O(\min \{m,n\})$. We use modulo $t$ for the indices. For a site $s\in \widehat{S}$, let $R(s)$ denote the region in $\mathrm{\Omega }$ bounded by $sp$, $sq$, $\beta (s)$, where $p$ and $q$ are two endpoints of $\beta (s)$. By Lemma 6, $V(s)\subseteq R(s)$. Observe that every spoke of $s$ intersecting $R(s)$ intersects $V(s)$. Let $n(s)$ denote the number of the spokes of $s$ intersecting $R(s)$. The total number of $n(s)$ for all $s\in \widehat{S}$ is $O(m)$ by Lemma 9.

We compute $\text{FV}(\widehat{S})$, which is the same as $\text{FV}(S)$. Roughly speaking, we partition a site sequence into two subsequences, $S_L$ and $S_R$, of roughly equal size, and compute $\text{FV}(S_L\cup S_R)$ by merging $\text{FV}(S_L)$ and $\text{FV}(S_R)$ along $\gamma (S_L,S_R)$ recursively. The bisector $\gamma (S_L,S_R)$ satisfies the property that any point of $\mathrm{\Omega }$ lying on one side of $\gamma (S_L,S_R)$ is farthest from some site in $S_L$ and any point of $\mathrm{\Omega }$ lying on the other side of $\gamma (S_L,S_R)$ is farthest from some site in $S_R$. Observe that $\gamma (S_L,S_R)$ is connected in $\mathrm{\Omega }$ with two distinct points on $\partial \mathrm{\Omega }$. If $\gamma (S_L,S_R)$ was not connected or it had more than two points on $\partial \mathrm{\Omega }$, it partitions $\partial \mathrm{\Omega }$ into four or more pieces, each belonging to either $\text{bFV}(S_L)$ or $\text{bFV}(S_R)$. Then the cells of $\text{bFV}(S_L)$ or $\text{bFV}(S_R)$ are not consecutive along $\partial \mathrm{\Omega }$, contradicting Lemma 8. Also, $\gamma (S_L,S_R)$ has no closed loop since no Voronoi cell in the loop is incident to $\partial \mathrm{\Omega }$.

Consider the $k$-th recursive step of the algorithm. Let $S_L$ and $S_R$ be two input sequences of sites in the step. We have $\text{FV}(S_L)$ and $\text{FV}(S_R)$. For a site $s\in S_L\cup S_R$, let $V_k(s)$ denote the cell of $s$ in $\text{FV}(S_L\cup S_R)$, and let $V_{k-1}(s)$ denote the cell of $s$ in $\text{FV}(S_L)$ for $s\in S_L$ and the cell of $s$ in $\text{FV}(S_R)$ for $s\in S_R$. Let ${\beta }_k(s)=V_k(s)\cap \partial \mathrm{\Omega }$ and $R_k(s)=R(s)\cap V_k(s)$. Let $R_{k-1}(S_L)={\bigcup }_{s\in S_L}{R}_{k-1}(s)$ and $R_{k-1}(S_R)={\bigcup }_{s\in S_R}{R}_{k-1}(s)$.

If three consecutive sites $s_{i-1},s_i,s_{i+1}$ are contained in $S_L\cup S_R$ for some $i$, ${\beta }_k(s_i)$ and $\beta (s_i)$ are the same. Thus, $V_k(s_i)\subseteq R(s_i)$ by Lemma 6, implying that $R_k(s_i)$ is $V_k(s_i)$.