Faster Planar Diameter using Pseudoline Envelopes

Introduction

Let $G$ be a directed graph with $n$ vertices, real edge weights $w : E \to\mathbb{R}$, and no negative weight cycles. Write $V(G)$ and $E(G)$ for the vertex and edge sets of $G$, and $d_G(u,v)$ for the length of a shortest directed $u$-to-$v$ path. We set $d_G(u,v) = +\infty$ when $v$ is unreachable from $u$, and $d_G(u,u) = 0$. In particular, $d_G(u,v)$ need not equal $d_G(v,u)$ in a directed graph. The outgoing eccentricity of $u$ and the diameter of $G$ are

Throughout the paper, eccentricity means outgoing eccentricity.

Computing the diameter of the graph is a fundamental problem in graph algorithms. For sparse graphs with $n$ vertices, $m = O(n)$ edges, and no negative weight edges, the simple algorithm of performing single source shortest path (SSSP) computation from every vertex runs in $\widetilde{O}(n^2)$ total time¹ using Dijkstra’s algorithm. Roditty and Vassilevska Williams [34] showed that assuming the strong exponential time hypothesis (SETH) and the orthogonal vectors (OV) hypothesis, there is no $O(n^{2-\varepsilon})$ time algorithm for any $\varepsilon> 0$. Since obtaining a truly subquadratic time is unlikely for general graphs, significant attention has turned to computing exact diameter in more structured families of graphs, such as bounded treewidth graphs [13, 3, 20, 4], planar graphs [6 GKM^{+}21, 17], minor-free graphs [15, 29, 25 CCG^{+}25, 35], and geometric intersection graphs [BKK^{+}22, DKP24, CGL24, CCG^{+}25, CCG^{+}26a, CCG^{+}26b].

In a celebrated 2017 breakthrough, Cabello [6] showed that diameter in weighted directed planar graphs can be computed in $\widetilde{O}(n^{11/6})$ running time. Gawrychowski, Kaplan, Mozes, Sharir and Weimann [GKM+21] subsequently improved the running time to $\widetilde{O}(n^{5/3})$. Central to both results is the understanding of additively weighted Voronoi diagrams for planar distances.

Voronoi diagram techniques crucially exploited planarity and thus did not readily extend to other graph classes. Progress in broader graph classes instead came from exploiting the combinatorial structure of distances through bounded VC-dimension. Ducoffe, Habib, and Viennot [15] first showed that subquadratic time diameter computation was possible in unweighted undirected minor-free graphs with a different structural technique involving distance VC-dimension. In a different approach, using the distance profile set systems that were shown to have bounded VC-dimension in planar graphs by Li and Parter [26], Le and Wulff-Nilsen [29] developed normalized distance profiles to obtain subquadratic diameter algorithms in unweighted minor-free digraphs. Zheng [35] recently extended the VC-dimension approach to handle minor-free digraphs with real edge weights.

Distance profile techniques have led to renewed progress on planar graphs. Recently, Fredslund-Hansen, Mozes, and Weimann [17] improved the running time for unweighted undirected planar graphs to $\widetilde{O}(n^{8/5})$ time by strengthening the Li and Parter [26] bound for planar distance profiles. This leaves a gap between $\widetilde{O}(n^{5/3})$ time for weighted directed planar graphs and $\widetilde{O}(n^{8/5})$ time in unweighted undirected planar graphs. Neither exponent seems to be optimal, raising the question of how far either bound can be improved.

Abboud, Mozes, and Weimann explicitly asked whether planar diameter admits an $n^{1+o(1)}$-time algorithm or whether a superlinear lower bound can be proved [1]. At the 2016 Dagstuhl seminar Structure and Hardness in P, Søren Dahlgaard suggested as an open problem that $n^{3/2-o(1)}$ conditional hardness was a possible target for planar diameter [27 Section 4.9]. The exponent $3/2$ also has a natural algorithmic motivation: the planar separator theorem of Lipton and Tarjan [28] guarantees a balanced separator with $O(\sqrt{n})$ vertices, and it is natural to need to consider all $O(n^{3/2})$ vertex–separator pairs in an algorithm to compute diameter. This makes $n^{3/2}$ time a natural milestone for planar diameter upper and lower bounds.

Results

We reach this natural $n^{3/2}$ milestone for weighted planar diameter.

The algorithm rests on a new structural theorem about planar shortest-path distances: normalized distance profiles form a family of pseudolines. Fix a face of a plane graph $H$ with vertices $s_1,s_2,\ldots,s_b$ ordered around the face. For every vertex $x \in V(H)$, the normalized distance profile is the sequence $\{d_H(s_i,x)-d_H(s_1,x)\}_{1\le i\le b}$. We prove that any two such profiles change relative order at most once as $i$ increases, meaning that this is a collection of pseudolines. See Figure 1 for an illustration. The most notable and surprising aspect of the new structural result is that $x$ is allowed to be anywhere in the graph. The standard Monge property of planar graphs applies only to pairs of vertices on a single face. This new structural result enables the usage of upper envelope and range searching techniques for planar distances.

A basic obstacle to applying range searching to graph distances is the size of the separator. The framework of Cabello and Knauer [13] organizes distances across a separator using orthogonal range searching, with dimension depending on the number of separator vertices. This dependence is effective for bounded-treewidth graphs that have constant sized balanced separators, but planar graphs can require balanced separators of size $\Theta(\sqrt{n})$. We show how to exploit planarity to avoid this. Instead we use Voronoi cells and the CCW-first ordering of [GKM+21] to organize the vertices into intervals, within each of which cell membership is determined by a single profile comparison. The pseudoline property allows us to build efficient data structures for performing this operation.

The resulting data structure removes a costly preprocessing step in the planar Voronoi approach to diameter. The construction of Gawrychowski et al. [GKM+21] uses $\widetilde{O}(Nb^2)$ preprocessing to compute the Voronoi diagram of an $N$-vertex graph with $b$ sites. This data structure supports farthest-vertex queries in a Voronoi cell. We present a new data structure that allows these farthest-vertex queries to be restricted to a prescribed subset $X \subseteq V(H)$, fixed during preprocessing: for each site $s$, we seek the farthest vertex from $s$ among the vertices of $X$ in its Voronoi cell. We call $X$ the target set. Writing $k = |X|$, our preprocessing takes only $\widetilde{O}(N+bk)$ time. This saves a factor of $b$ when all vertices are targets, while its dependence on $k$ allows us to preserve distances in a large graph and optimize over a much smaller region. Combining this structure with the fast Voronoi construction of Mozes and Prigan [31] and a recursive planar decomposition gives the $\widetilde{O}(n^{3/2})$ running time.

Geometry of distances between boundaries and interiors Monge inequalities have long been useful in computing distances in planar graphs, as in FR-Dijkstra [18]. The connection between Monge matrices and pseudolines have been exploited previously [21, 23, 12] for matrix searching. However, the standard Monge argument only applies to distance matrices of vertices that lie on a single face. Our new theorem can be viewed as a proof that the normalized distance matrix between vertices on a single face and vertices anywhere else (after sorting rows and columns appropriately) is a totally monotone, a condition that is weaker than Monge.

Technical Overview

We give an overview of our techniques to compute all vertex eccentricities, and hence diameter of a directed plane graph $G$. A key step is to do local computation on a strongly connected subgraph $H$ of $G$ with $N$ vertices and a set $B = \{s_1, \ldots, s_b\}$ of $b$ vertices on a face that separates $H$ from some subset of vertices $Y \subseteq V(G)$. To compute the farthest vertex in $H$ from a vertex $y \in Y$, we define a function $\omega: B \to\mathbb{R}$ where $\omega(s) = d_G(y,s)$ for $s \in B$, and find a vertex $x \in V(H)$ that maximizes $d_G(y,x)$. In notation this is:

To do so, we utilize Voronoi diagrams.

Voronoi Diagrams For additive weights $\omega: B \to\mathbb{R}$, we say that the weights are admissible, if for every $u,v \in B$, it holds that $\omega(u) + d_H(u,v) \geq\omega(v)$ so the triangle inequality is respected. Note that shortest path distances in any graph satisfy triangle inequality and are thus admissible. Define the Voronoi cell of a boundary vertex $s \in B$ as

For simplicity we assume that no ties occur so these cells partition $V(H)$ and form the additively weighted Voronoi diagram $\operatorname{VD}(H,B,\omega)$. A Voronoi cell is represented in the dual graph, and for any $s \in B$, the boundary of the Voronoi cell $\operatorname{Vor}(s)$ is a collection of dual edges and faces and is denoted by $\partial\operatorname{Vor}(s)$. The diagram has a compact reduced dual representation of total complexity $O(b)$, and a represented edge may stand for a long path of underlying dual edges. The complexity of the Voronoi cell $|\partial\operatorname{Vor}(s)|$ is measured by the number of faces that contain a vertex of $\operatorname{Vor}(s)$ and vertices of at least two other Voronoi cells. A standard fact (see [6] or [GKM+21, Corollary 2.3]) is that a Voronoi diagram of $b$ sites has total complexity $\sum_{s\in B}|\partial\operatorname{Vor}(s)| = O(b)$.

Farthest vertex in Voronoi cells The Voronoi diagram gives us a way to compute the distances:

Gawrychowski, Kaplan, Mozes, Sharir, and Weimann [GKM+21, Theorem 1.1] provide such a data structure for $N$-vertex planar graphs with no negative weight cycles and $b$ vertices lying on $O(1)$ faces. After $\widetilde{O}(Nb^2)$ preprocessing time, their data structure constructs the diagram for any admissible additive weight $\omega$ in $\widetilde{O}(b)$ time. It then computes the maximum distance from each active site $s$ to a vertex in $\operatorname{Vor}(s)$ in $\widetilde{O}(|\partial\operatorname{Vor}(s)|)$ time. Thus, both constructing the diagram and computing all cell maxima take $\widetilde{O}(b)$ total time.

The most expensive part is preprocessing, not query time. For each pair of boundary vertices, their construction preprocesses all possible bisectors as the difference between the two additive weights varies. A fixed pair of boundary vertices requires $\widetilde{O}(N)$ time and space to handle. Processing all $\Theta(b^2)$ pairs therefore incurs $\widetilde{O}(Nb^2)$ preprocessing time [GKM+21]. We avoid this pairwise preprocessing by using distance profiles that we will define shortly. When the sites lie on a single face, our data structure supports searching for the maximum among a fixed target subset of vertices $X$ with preprocessing time sensitive to its size. The following is our main data structure contribution.

The target vertex set $X$ is fixed during preprocessing, while the additive weights $\omega$ are supplied with each query. In the diameter algorithm, the graph we are building the data structure on may be much larger than $|X|$, making this refined preprocessing time essential.

Distance profiles and pseudolines Fix an arbitrary vertex, say $s_1\in B$, where the vertices $B=\{s_1,s_2,\ldots,s_b\}$ are ordered counterclockwise around a single face. Define the normalized distance profile of a target $x\in X$ as

These were examined by Le and Wulff-Nilsen [29] which were inspired by the patterns of Li and Parter [26]. The crucial observation is that viewing the distance profile as a (discrete) curve going through the points $(1, f^{s_1}_{x}(s_1)), (2, f^{s_1}_{x}(s_2)), \ldots, (b, f^{s_1}_{x}(s_b))$, these curves satisfy a pseudoline property: two curves change relative order at most once along the boundary. See Figure 1 for an illustration of this. The proof of this follows from a variation of the result of Li and Parter [26], who show that unweighted graphs avoid alternating patterns. The pseudoline property indicates that these profiles behave similarly to abstract lines in the plane. In particular, this implies upper envelopes of $k$ pseudolines have complexity $O(k)$.

Handling a query For each query, we construct the additively weighted Voronoi diagram with the recent fast construction algorithm of Mozes and Prigan [31] in $\widetilde{O}(b)$ time. We then use the fact that the Voronoi edges of $\operatorname{Vor}(s_1)$ partition the $CCW$-first ordering of the shortest-path tree $T_{s_1}$ rooted at $s_1$ into one circular interval per Voronoi edge, as observed in [GKM+21]. The cell $\operatorname{Vor}(s_1)$ induces a connected subtree of $T_{s_1}$, and each excursion of the tree traversal outside the cell visits an entire attached subtree before returning. The outward edges of the cell occur in the order of its dual boundary, so all excursions through the same reduced Voronoi edge lie in its corresponding interval. See § 5.1 for details and Figure 3 for an illustration. On the interval corresponding to an edge separating the Voronoi cells of $s_1$ and $s_i$, membership in the Voronoi cell of $s_1$ is determined by the single comparison $f^{s_1}_{x}(s_i) > \omega(s_1) - \omega(s_i)$. For an $x$ outside $\operatorname{Vor}(s_1)$ in the interval, the shortest path from $s_1$ to $x$ first leaves $\operatorname{Vor}(s_1)$ at a vertex $v \in\operatorname{Vor}(s_i)$. Replacing the $s_1$-to-$v$ prefix by a shortest path from $s_i$ to $v$ yields $f^{s_1}_{x}(s_i) < \omega(s_1) - \omega(s_i)$, so the comparison with $s_i$ alone excludes every vertex outside $\operatorname{Vor}(s_1)$ in the interval.

We find the farthest vertex of $\operatorname{Vor}(s_1) \cap X$ within a $CCW$-first interval $I$ by binary searching the sorted distances $d_H(s_1,x)$ for $x \in X$. For a candidate distance $D$, we consider targets whose $CCW$-first positions lie in $I$ and whose distances from $s_1$ are at least $D$. A data structure on $CCW$-first positions and distances decomposes the candidate set into polylogarithmically many canonical subsets, whose upper envelopes are stored during preprocessing. If the largest envelope value at $s_i$ exceeds $\omega(s_1) - \omega(s_i)$, the vertex $x$ corresponding to a maximizing profile $f^{s_1}_{x}$ belongs to $\operatorname{Vor}(s_1)$ and satisfies $d_H(s_1,x) \ge D$; otherwise, no candidate belongs to $\operatorname{Vor}(s_1)$. The pseudoline property of normalized distance profiles shows that these upper envelopes have linear complexity. Standard range searching then achieves $\widetilde{O}(bk)$ preprocessing for the $k$ target vertices, in addition to $\widetilde{O}(N)$ shared global preprocessing. The reduced Voronoi diagram has $O(b)$ Voronoi edges, each representing a bisector between two sites and defining one interval in the $CCW$-first ordering rooted at each of the two sites. Thus, processing the resulting $O(b)$ intervals in $\widetilde{O}(1)$ time per interval gives $\widetilde{O}(b)$ total query time.

From data structure queries to diameter. We apply the data structure within a recursive $r$-division with few holes [24]. The important insight is that it suffices to handle distances between vertices on successive levels of the $r$-division. This way, we can separately consider the holes of each piece of the division in every level of the hierarchy as a single face to apply Theorem 2. Pairs of vertices between these successive levels and the remaining pairs at the leaves account for every pair of vertices in the graph. Each vertex maintains the greatest distance found, yielding eccentricities and hence the diameter.

Organization

We begin with preliminaries in § 2, before presenting the full algorithm for diameter and eccentricities using our data structure of Theorem 2 in § 3. Next, we analyze the structural connection between distance profiles and pseudolines in § 4 before proving Theorem 2 in § 5.

Preliminaries

Unless stated otherwise, $G$ is a directed planar graph with $n = |V|$ vertices and $O(n)$ edges with a weight function $w(e) = w(u,v)$ for each edge $(u,v)$. We assume $G$ has no negative weight cycles. For a subgraph $H \subseteq G$ with $N$ vertices, we use $V(H)$ to denote the vertices of $H$, and $E(H)$ to denote the edges of $H$. We designate a face of $H$ as the outer face and let $B$ be the set of vertices on the boundary. A plane graph is a planar graph with a fixed embedding. Connectivity, faces, and planar duality refer to the underlying undirected embedded graph. We write $e^*$ and $f^*$ for the dual edge of a primal edge $e$ and the dual vertex of a face $f$.

Simplifying assumptions. For the weighted algorithm for computing eccentricities, we will assume that the undirected version of the input planar graph is simple and maximal (thus triangulated), and we have weighted directed edges going in both directions (so the graph is strongly connected). We justify these assumptions as follows. We can remove self-loops and for each ordered pair of adjacent vertices, retain only a shortest directed edge. Define $M = \sum_{e \in E(G)} |w(e)|$. Every reachable pair has a shortest simple path of absolute value at most $M$. Add edges to any embedding of the graph to make it maximal, giving length $2M + 1$ to both directions of every added edge and to each missing reverse directed edge. Note that for any two vertices $u,v \in V(G)$ where $u$ can reach $v$, the shortest path distance did not change by the transformation. On the other hand if $u$ cannot reach $v$, the shortest path distance will be at least $2M + 1 - M = M + 1$, as the sum of all original edges is at least $-M$. Thus if a shortest path from $u$ to $v$ is larger than $M$ in the augmented graph, then $u$ does not reach $v$ in the original graph. Furthermore, we can assume that the lengths of all shortest paths are unique. This can be done by standard symbolic perturbation of the edges.

Recursive subdivisions A region of a planar graph is an edge-induced embedded subgraph where we ignore edge orientations. A division covers the edges of the graph by regions, which may overlap on their boundaries. A vertex shared by multiple regions is a boundary vertex. The boundary vertices of a region $R$ are denoted by $\partial R$. A hole of $R$ is a face of $R$ that is not a face of the original embedded graph. An $r$-division is a division with $O(n/r)$ regions, each with at most $r$ vertices and $O(\sqrt{r})$ boundary vertices. It has few holes if each region has $O(1)$ holes and every edge shared by two regions lies on a hole boundary in each of them [citep][KMS13].

A decomposition tree is a rooted hierarchy of regions whose root is the entire graph and whose children cover their parent. For a geometrically decreasing sequence $\mathbf{r} = (r_m,\ldots,r_1)$, a recursive $r$-division with few holes is such a hierarchy where each level is a $r_i$-division with few holes.

We use the connected regions produced by this construction [citep][KMS13], Section 2.5). At scale $r$, there are $O(n/r)$ regions, each of size $O(r)$, with $O(\sqrt{r})$ boundary vertices and $O(1)$ holes.

Multiple-source shortest paths (MSSP). For a strongly connected planar graph $H$, let $T_s$ denote the shortest-path tree rooted at $s$, with tree edges directed away from $s$.

We use the multiple-source shortest-path (MSSP) algorithm of Klein [citep][Kle05]. For a fixed face $B$ of an $N$-vertex planar graph $H$, the algorithm moves the root of the shortest-path tree around the boundary of $B$. Over the entire execution, the shortest-path tree undergoes only $O(N)$ changes, and a persistent representation gives access to the tree rooted at each boundary vertex.

Note that the original algorithm of [22] could only handle nonnegative edge weights. Mozes and Wulff-Nilsen [32] show that by vertex reweighting, this can be extended to any graph with no negative weight cycle with $O(N \log^{2} N / \log\log N)$ additional preprocessing time.

Distance oracle. We will need exact distances between arbitrary ordered pairs of vertices. We use the distance oracle of Charalampopoulos et al. [10], with the improved construction of Mozes and Prigan [31].

Weighted Eccentricities and Diameter Algorithm

We prove Theorem 1 by applying the Voronoi farthest vertex data structure of Theorem 2 separately within each hole of a recursive division. The high level strategy is to construct a recursive $r$-division with few holes and consider each parent-child pair of regions $(P,Q)$. For each hole $h$ of $Q$, we query distances from vertices of $Q$ to vertices of $P$ lying in $h$ or on its boundary.

Recall that the input is an $n$-vertex planar graph $G$ that is strongly connected and triangulated. We present the entire algorithm here for computing the eccentricities of all vertices.

1. Construct a global distance oracle. Construct a single distance oracle on the entire graph $G$ using Theorem 5. This oracle is used in steps 4(b) and 4(c) of the algorithm.

2. Construct a recursive $r$-division. Construct a recursive $r$-division with few holes of Theorem 3, with geometrically decreasing scales $r=(r_m,\ldots,r_1)$ and $r_1=L$ for a parameter $L$ we will specify later.

3. Initialize the answers. For every vertex $u \in V(G)$, let $A[u]$ denote its tentative eccentricity and $W[u]$ denote a vertex witnessing this value. Initialize $A[u]=0$ and $W[u]=u$.

4. Process distances. For every parent-child pair $(P,Q)$ in the hierarchy, perform Steps 4(a) and 4(b) separately for each hole $h$ of $Q$, separating $Q$ from $P \setminus Q$, including the exterior hole when present. Let $B_h$ be the boundary walk around the hole $h$. (If the hole $h$ is not simple, e.g. because of pendant vertices or bridges, perform the standard transformation of adding an additional copy of each vertex for each occurrence in a facial walk and add zero weight edges to make the boundary simple.) Note that Step 4(c) is performed only when $Q$ is a leaf.

   (a) Build the local data structures. Define $H_{P,h}$ by retaining the part of $G$ drawn in $h$, together with its boundary $B_h$. Thus $V(H_{P,h}) \cap V(Q)=V(B_h)$. (Note that $H_{P,h}$ does not contain $Q$.) Using Theorem 2, choosing $X=V(P)\cap V(H_{P,h})$, construct the implicit data structure for querying $\operatorname{VD}(H_{P,h},B_h,\omega)$ for $\omega$ defined by vertices within $Q$.

   (b) Handle child to parent distances. For every vertex $u \in V(Q)$, query the global distance oracle of Step 1 to obtain the additive boundary weights $\omega_u(s)=d_G(u,s)$ for $s \in B_h$. Using the implicit data structure for $\operatorname{VD}(H_{P,h},B_h,\omega_u)$, query with the additive weights $\omega_u$ to compute the farthest vertex from $u$ in $\operatorname{Vor}(s)\cap V(P)$ for all $s \in B_h$, updating $A[u]$ and $W[u]$ if a farther vertex is found. The distances used within the Voronoi data structure remain $d_{H_{P,h}}$.

   (c) Handle distances within leaves. If $Q$ is a leaf, query the global distance oracle for $d_G(u,v)$ for every ordered pair $(u,v)\in V(Q)\times V(Q)$. Update $A[u]$ and $W[u]$ if a farther vertex is found. These distances are computed in the full graph $G$ using the distance oracles of Step 1.

At the end of the algorithm, we will have computed the eccentricity of every vertex $u \in V(G)$ as $A[u]$ and a witness to the eccentricity $W[u]$. The diameter can be computed as the maximum eccentricity.

Correctness

Fix a vertex $u \in V(G)$ with $u \in V(Q_u)$ for a leaf region $Q_u$. Suppose the eccentricity of $u$ is witnessed by a vertex $t \in V(G)$. We divide into two cases depending on whether $t \in Q_u$. In either case, we show that we have considered the distance from $u$ to $t$ as a candidate for eccentricity. We also show that every candidate considered in Steps 4(b) and 4(c) is an exact distance in $G$, and hence cannot exceed the eccentricity of $u$; together with coverage, this proves correctness.

Coverage of leaf distances Suppose $t \in Q_u$. Step 4(c) queries the global distance oracle for every ordered pair of vertices in $V(Q_u)$. In particular, the oracle returns the exact distance $d_G(u,t)$, even if a shortest path leaves and reenters $Q_u$. This distance is considered as a candidate for the eccentricity of $u$.

Coverage of non-leaf distances Suppose that $t \notin Q_u$. Then there must be some parent and child region $P$ and $Q$ with $u \in Q$, and $t \in P \setminus Q$ where $h$ is the hole of $Q$ containing $t$, with boundary $B_h$. The piece $Q$ can be found by walking up the hierarchy from $Q_u$ until we find that $t \in P$. Step 4(b) queries the global distance oracle to obtain $\omega_u(s) = d_G(u,s)$ for every $s \in B_h$, and constructs an implicit representation of $\operatorname{VD}(H_{P,h}, B_h, \omega_u)$.

The following argument applies to every processed parent-child pair $(P,Q)$, every hole $h$ of $Q$, and every source $u \in V(Q)$. For every $v \in V(H_{P,h})$, splitting a shortest $u$-to-$v$ path at its last vertex of $B_h$ gives $d_G(u,v) = \min_{b \in B_h}\{\omega_u(b) + d_{H_{P,h}}(b,v)\}$, since the remaining suffix lies in $H_{P,h}$. Thus, for every $v \in\operatorname{Vor}(s)$, the value $\omega_u(s) + d_{H_{P,h}}(s,v)$ equals $d_G(u,v)$, so we have considered correct shortest paths for all candidates considered.

Suppose $t \in\operatorname{Vor}(s) \cap V(P)$ for $s \in B_h$. The data structure of Theorem 2 returns the farthest vertex in $\operatorname{Vor}(s) \cap V(P)$, suppose it returned some vertex $v'$. Thus $v'$ satisfies the expression as follows.

Thus we have considered a distance $d_G(u,v') \ge d_G(u,t)$ as a candidate for the eccentricity of $u$. Since $t$ witnesses the eccentricity of $u$, equality follows, and $v'$ is therefore globally farthest from $u$.

Running time

The global distance oracle of Step 1 is constructed once in $n^{1+o(1)}$ time using Theorem 5. Step 2 takes $O(n)$ time using Theorem 3.

To analyze Step 4, consider a child region $Q$ at scale $r_i$ of the recursive $r$-division, its parent $P$, and a hole $h$ of $Q$. In particular, this means that both $P$ and $Q$ have size $O(r_i)$, and the boundary hole $B_h$ has size $b = O(\sqrt{r_i})$. Step 4(a) applies Theorem 2 to $H_{P,h}$ of size $O(n)$, with $|B_h| = O(\sqrt{r_i})$ and $|X| = O(r_i)$. This takes $\widetilde{O}(n + r_i^{3/2})$ preprocessing time.

Step 4(b) makes $O(|V(Q)||B_h|) = O(r_i^{3/2})$ oracle queries to obtain the additive weights, taking $O(r_i^{3/2}\log^{2+o(1)} n) = \widetilde{O}(r_i^{3/2})$ time. For each of the $O(r_i)$ vertices of $Q$, constructing $\operatorname{VD}(H_{P,h}, B_h, \omega_u)$ takes $\widetilde{O}(b)$ time by Theorem 2. Querying all Voronoi cells takes $\widetilde{O}(\sum_{s \in B_h} |\partial\operatorname{Vor}(s)|) = \widetilde{O}(\sqrt{r_i})$ time for each $\omega_u$, taking $\widetilde{O}(r_i^{3/2})$ time in total. Step 4(c) makes $O(|V(Q)|^2) = O(L^2)$ oracle queries per leaf, taking $\widetilde{O}(L^2)$ time per leaf and $\widetilde{O}(nL)$ time over all leaves, since all leaves have size at most $L$. Using the fact that there are $O(n/r_i)$ many regions at scale $r_i$, and that each child region has $O(1)$ holes, so processing all its holes changes the bounds for Steps 4(a) and 4(b) by only a constant factor. Therefore, the total running time is:

The last equality uses that the scales are geometric, with minimum $L$ and maximum $O(n)$. Setting $L=\sqrt{n}$ balances the terms $nL$ and $n^2/L$ and gives $\widetilde{O}(n^{3/2})$ time.

Pseudoline Families

Here we give a careful definition of weak pseudoline families that allow for stretches of equality between the pseudolines, before showing that normalized distance profiles form a pseudoline family. Subsequently, we describe efficient data structures for constructing upper envelopes of distance profile pseudolines.

Characterizing Pseudolines

In this section we define what it means for a family of discrete functions to be pseudolines. We say that the collection of functions $f_1,\ldots,f_k:[b]\to\mathbb{R}$ is a weak pseudoline family, if the ordered list of differences $\{f_i(x)-f_j(x)\}_{x\in[b]}$ switches signs at most once after omitting all zero entries. This induces a geometric belowness relationship: we can say $f_i$ is weakly below $f_j$ at $x$, or in notation $f_i(x)\prec f_j(x)$. These functions are called pseudolines because if $f_i$ is initially below $f_j$, then there is at most one point where $f_i$ transitions to being weakly above $f_j$, and $f_i$ will never be below $f_j$ afterwards. We formally characterize this relation as it will be useful in our later algorithms.

Definition 6. Let $b$ be a positive integer and consider $k$ discrete functions $f_1,\ldots,f_k:[b]\to\mathbb{R}$. For $i,j\in[k]$ and $x\in[b]$, we can say that $f_i(x)\prec f_j(x)$ if the function $f_i$ lies weakly below $f_j$ at $x$, meaning that one of the following holds:

1. Strictly below. $f_i(x)<f_j(x)$.

2. Weakly below. $f_i(x)=f_j(x)$ and either:

   (a) $f_i(y)=f_j(y)$ for all $z<y\le x$ and $f_i(z)<f_j(z)$ for some $1\le z<x$.

   (b) $f_i(y)=f_j(y)$ for all $1\le y<z$ and $f_i(z)<f_j(z)$ for some $x<z\le b$.

   (c) $f_i(y)=f_j(y)$ for all $1\le y\le b$ and $i<j$.

This definition of a weak pseudoline family allows for stretches of equality and thus is slightly different from the standard definition of pseudolines in [2], but remark that they can be handled in essentially the same way (e.g. if you first make infinitesimal perturbations). We justify why we need this more cumbersome definition to handle these stretches of equality in an example in next section.

Normalized Distance Profiles form a Pseudoline Family

Recall that we consider a planar graph $H$, with a specific identified face $B=\{s_1,\ldots,s_b\}$. Without loss of generality, we may assume that $B$ is the outer face. Recall also the definition of the normalized distance profiles:

Data Structures for Upper Envelope of Distance Profile Pseudolines

These distance profiles have stretches of equality for technical reasons: there can be stretches of equality between two distance profiles that arise naturally from the shortest path topology. As an example consider two vertices $x,y \in V(H)$, where $y$ lies on the shortest path between $s_1$ and $x$ as well as on the shortest path between $s_2$ and $x$. In this case

We prove here that normalized distance profiles $\{f_x^{s_1}\}_{x\in V(H)}$ form a weak pseudoline family by adapting the argument of Li and Parter [26]. Their argument was only for unweighted profiles, where they instead analyzed the discrete derivative of the distance profile $\{f_x^{s_1}(s_i)-f_x^{s_1}(s_{i-1})\}_{i=2,\ldots,b}$. We generalize the argument to weighted profiles.

Data Structures for Upper Envelope of Distance Profile Pseudolines

In this section we discuss basic computation of upper envelopes, and describe a data structure to quickly compute upper envelopes of distance profiles around different boundary vertices.

Constructing upper envelopes We begin by considering two basic geometric primitives to manipulate pseudoline families.

1. Point comparison. Given two $x,y \in X$ and a point $s_i$, decide if $f_x^s(s_i) \prec f_y^s(s_i)$.

2. Locating a crossing. Given two $x,y \in X$, find the smallest $i$ such that $f_x^s(s_i) \succ f_y^s(s_i)$ or report that none exist.

If these geometric primitives can be implemented in $\widetilde{O}(1)$ time, we can compute the upper envelope with any algorithm, e.g. Graham’s scan [33]. Graham’s scan sorts the vertices of $X = \{x_1,\ldots,x_k\}$ such that $f_{x_1}^s(s_1) \succ f_{x_2}^s(s_1) \succ\cdots\succ f_{x_k}^s(s_1)$, and then processes each pseudoline in this order from first to last, building the upper envelopes using a stack.

Geometric primitives for distance profiles Here we show that point comparisons and locating a crossing can be performed in $\widetilde{O}(1)$ time for any collection of $k$ distance profiles $\{f_x^s\}_{x\in X}$ for any of the $b$ choices of $s \in B$ (when we choose a different $s$ we rotate the labels on all the sites so $s$ appears first on the boundary ordering) on the boundary after $\widetilde{O}(bk)$ preprocessing. This is notable because to specify a single distance profile requires $O(b)$ space, and there are $bk$ many pseudolines of the form $f_x^s$, so a naive implementation could require $O(b^2k)$ preprocessing. Conveniently, any fixed $x \in X$ and any $s_i,s_j \in B$, the distance profiles $f_x^{s_i}$ can be obtained from $f_x^{s_j}$ by shifting all coordinates by an additive constant $d_H(s_j,x)-d_H(s_i,x)$. Our following data structure is able to leverage this fact by exploiting the fact that this transformation preserves differences between adjacent points.

Proof. The explicit distance matrix gives the $bk$ values of $f_x^s(s_i)$ for all $s_i \in B$ and $x \in X$. It will be convenient for us to consider the discrete differences of adjacent values $D_x[s_i] = f_x^s(s_{i-1}\pmod b)-f_x^s(s_i)$, where we define $s_0=s_b$. Observe that this does not depend on the choice of basepoint $s$, so there are at most $bk$ such values. After sorting these $bk$ values, we can translate the entries into rank space so all values are integers between 1 and $bk$, without changing the answer to any comparison between them.

Point Comparison To handle point comparisons between $f_x^s(s_i)$ and $f_y^s(s_i)$, we can directly compute both values. If they are not equal, we are done. Otherwise $f_x^s(s_i)=f_y^s(s_i)$, we will lexicographically compare the following discrete difference strings:

Suppose $K_x^s(i) \ne K_y^s(i)$. Let $j$ be the largest value where $D_x[s_j] \ne D_y[s_j]$. Interchanging $x$ and $y$ if necessary, assume that $D_x[s_j] < D_y[s_j]$. As $f_x^s(s_i)=f_y^s(s_i)$, we have that

and that $f_x^s(s_{j-1}) < f_y^s(s_{j-1})$. Thus we can safely conclude that $f_x^s(s_i) < f_y^s(s_i)$.

Otherwise $\overline{K}_x^s(i) = \overline{K}_y^s(i)$ and all values of $f_x^s(s_\ell) = f_y^s(s_\ell)$ for all $1 \le\ell\le i$. Then we must look ahead for a crossing:

A similar argument allows us to decide if $f_x^s(s_i) < f_y^s(s_i)$.

To handle these comparisons between strings, we consider the suffix array data structure [30] that allows for lexicographical comparisons of arbitrary substrings (contiguous subsets) in $\widetilde{O}(1)$ time. Furthermore, we remark that for different base vertices $s \in B$, all strings of the form $\overline{K}_x^s(i)$ (and $\overline{K}_y^s(i)$) are substrings of the (reversed) doubled discrete distance string:

Thus we can build two single suffix array in $\widetilde{O}(bk)$ time over the strings $\widetilde{D}_x$ and their reverse for all $x \in X$ to handle these queries for all boundary vertices $s \in B$ in $\widetilde{O}(1)$ time.

Locating a Crossing. There can be at most one crossing between any two pseudolines. If initially we have $f_x^s(s_1) \prec f_y^s(s_1)$, and for some later $i$ we have $f_x^s(s_i) \succ f_y^s(s_i)$, then $f_x^s(s_j) \succ f_y^s(s_j)$ for all $j > i$. Thus we can binary search for the smallest $i$ with $O(\log b)$ calls to point comparison.

Combining Lemma 9 with Theorem 8 yields the following theorem.

Farthest Vertex Data Structure

The main objective of this section is to prove the existence of the farthest vertex data structure of Theorem 2. To do so, we will first describe a way to order the edges in § 5.1. We then show in § 5.2 that it suffices to make a single data structure query with a contiguous interval in this ordering for each Voronoi edge of a Voronoi cell to find the farthest vertex. § 5.3 shows that we can compute such intervals efficiently. § 5.4 shows how the interval query can be handled by a reduction to computing pseudoline upper envelopes. Finally, we conclude by putting everything together to prove Theorem 2 in § 5.5.

Recall that $H$ is an $N$-vertex planar graph with bidirected edges (possibly with different weights in each direction) and a collection of sites $B = (s_1,\ldots,s_b)$ that lie in this order on the outer face of $H$. Let $T_i$ denote the shortest path tree rooted at $s_i$.

CCW-First Ordering

We use the CCW-first ordering of [GKM+21] to assign distinct indices to the vertices and directed edges of $H$. For every directed edge $e = (u,v)$, add an artificial leaf $x_e$ adjacent to $u$, placing its edge immediately before $e$ in the counterclockwise order around $u$. For a boundary root $s_i$, let $T_i^+$ consist of the shortest path tree $T_i$ and all artificial leaf edges.

Perform a depth-first traversal of $T_i^+$, visiting the children of each vertex in counterclockwise order, starting immediately after the edge to its parent. At $s_i$, start from a fixed imaginary incoming edge embedded in the outer face. Let $\operatorname{pre}_i(z)$ be the preorder index of a vertex $z$ in this traversal, starting with $\operatorname{pre}_i(s_i)=0$. Define the CCW-first index of a directed edge $e$ by $\rho_i(e)=\operatorname{pre}_i(x_e)$. Every original vertex and every directed edge has a distinct index, including both directions of tree and non-tree edges.

We next show how to compute these indices for trees rooted at each boundary vertex $s_i \in B$ with only $\widetilde{O}(N)$ total preprocessing.

Proof. We use MSSP to maintain the shortest path tree as the source moves around the outer face. Following [10 Appendix A.2], we use a fixed auxiliary root $r$ embedded in that face. Add to $T_i$ an additional edge $(r,s_i)$, placed at the prescribed imaginary incoming edge of $s_i$. MSSP performs $O(N)$ parent changes of the form $T \leftarrow T - \{(p,v)\} + \{(q,v)\}$, where $q$ lies outside the subtree rooted at $v$.

We maintain the Euler tour of the augmented tree, traversing each tree edge in both directions and following the counterclockwise edge order at each vertex. Store the Euler tour in a balanced binary tree supporting splits, concatenations, and prefix sums. Give value 1 to edges moving away from $r$, and value 0 otherwise. These edges mark the first time a vertex $v \in V(H)$ or an artificial leaf $x_e$ is visited. To compute $\operatorname{pre}_i(v)$, we take the prefix sum of the Euler tour before the traversal from its parent. The same query for the artificial leaf $x_e$ gives $\rho_i(e)$.

An MSSP parent change detaches the subtree rooted at $v$ and inserts it at the position of $(q,v)$ in the counterclockwise edge order at $q$. Since the incoming edge at $v$ also changes, we cyclically rotate the detached subtree tour to start immediately after the new parent edge. This requires only $O(1)$ splits and concatenations, together with replacing the two occurrences of the old parent edge. We also update the pointer to the first arrival at $v$. Thus each change takes $O(\log N)$ time.

Finally, we make the binary tree storing the Euler tour persistent across the MSSP changes, and keep a version for every tree $T_i$ rooted at a boundary vertex $s_i \in B$. Since MSSP makes $O(N)$ tree changes, maintaining the Euler tours takes $O(N \log N)$ time since each split and concatenation takes $O(\log N)$ time. Persistence costs an extra $O(\log N)$ factor in preprocessing time and query time. Thus the total preprocessing time and space are $\widetilde{O}(N)$, and each query takes $\widetilde{O}(1)$ time.

Remark. The artificial leaves allow us to query $\rho_i(e)$ directly even when $e$ does not belong to $T_i$. For a fixed target vertex set $X$ of size $k$, we can also compute $\operatorname{pre}_i(x)$ for all $s_i \in B$ and $x \in X$, and sort $X$ in each ordering, in $\widetilde{O}(bk)$ additional time. Thus representing the orderings and extracting their restrictions to $X$ takes $\widetilde{O}(N+bk)$ total preprocessing time and space.

Voronoi Cells and Shortest Path Trees

We will discuss the interaction between the Voronoi cell $\operatorname{Vor}(s)$ for some $s=s_i \in B$ in the Voronoi diagram $\operatorname{VD}(H,B,\omega)$ with respect to arbitrary admissible weights $\omega$, the shortest path tree $T_i$, and a CCW-first index of the edges. Let $E_1,\ldots,E_d$ be the edges of the reduced dual Voronoi diagram of $\operatorname{Vor}(s)$ in counterclockwise order around the Voronoi cell. Each reduced Voronoi edge consists of a set of dual edges that separate $\operatorname{Vor}(s)$ from another Voronoi cell $\operatorname{Vor}(s_{j_\ell})$. Let $e_\ell=(u_\ell,v_\ell)$ be the directed primal edge whose dual is the first edge of $E_\ell$ encountered in a counterclockwise walk around the boundary of $\operatorname{Vor}(s)$, oriented so that $u_\ell\in\operatorname{Vor}(s)$ and $v_\ell\in\operatorname{Vor}(s_{j_\ell})$. Let $J_\ell$ consist of the original vertices $x$ whose positions $\operatorname{pre}_i(x)$ lie in the cyclic interval $[\rho_i(e_\ell),\rho_i(e_{\ell+1}))$, where the interval for the last reduced edge $E_d$ ends at $\rho_i(e_1)$. If $d=1$, this interval comprises one complete traversal. The following lemma relates these intervals to the structure of $\operatorname{Vor}(s)$ in $T_i$ and shows that, within each $J_\ell$, membership in $\operatorname{Vor}(s)$ is determined by a single comparison with the neighboring site $s_{j_\ell}$.

Proof. We begin by showing that normalized distance profiles are monotone non-increasing as we walk down the shortest path tree. Consider a vertex $v$ with parent $p$ in $T$. As the edge $e=pv$ lies on the shortest path from $s$ to $v$, we have that $d_H(s,v)=d_H(s,p)+w(e)$. For any other site $t$, triangle inequality gives $d_H(t,v)\leq d_H(t,p)+w(e)$. Subtracting this yields:

Proof of (a) connected Voronoi subtrees. A vertex $x\in V(H)$ is in $\operatorname{Vor}(s)$ if $x$ is closer to $s$ than any other site. This means that $f_x^s(t)\geq\omega(s)-\omega(t)$ for every other $t\in B$. Thus if $x$ has parent $p$ in $T$, then for every $t\in B$ we must have $f_p^s(t)\geq f_x^s(t)\geq\omega(s)-\omega(t)$. By induction, the entire shortest path from $s$ to $x$ is in $\operatorname{Vor}(s)$. Thus we conclude that $\operatorname{Vor}(s)$ is a connected subtree.

Proof of (b) Voronoi edges give CCW-first intervals. Let $\Gamma$ be the boundary walk of $\operatorname{Vor}(s)$ in the dual. By part (a), the paths in $T$ from $s$ to the tails of the edges leaving $\operatorname{Vor}(s)$ lie entirely in $\operatorname{Vor}(s)$. These paths are non-crossing, and the CCW-first search explores their branches in counterclockwise order. Thus, contracting the subtree of $T$ induced by $\operatorname{Vor}(s)$ to $s$ preserves the cyclic order in which the search encounters the outward boundary edges. After contraction, these edges occur counterclockwise around $s$ in the order of their duals along $\Gamma$, so the cyclic order of the reduced Voronoi edges agrees with the CCW-first order.

Each reduced Voronoi edge $E_\ell$ is a contiguous subpath of $\Gamma$. Thus the outward directed primal edges whose duals belong to $E_\ell$ occur consecutively among the outward boundary edges encountered by the CCW-first search. Say $e^*\in E_\ell$ is an edge dual to the primal edge $e$ of $T$ and $C_e$ is the connected component of $T-\operatorname{Vor}(s)$. Once the tour enters $C_e$ through the edge $e$, it visits the entire rooted subtree $C_e$ before returning to $\operatorname{Vor}(s)$. Every interval endpoint is the index of an artificial leaf attached to a vertex of $\operatorname{Vor}(s)$, so no endpoint is encountered during this excursion. Since $\rho_i(e)$ lies in $[\rho_i(e_\ell),\rho_i(e_{\ell+1}))$ and is visited immediately before entering $C_e$, the entire CCW-first traversal of $C_e$ lies in this cyclic interval. See Figure 3 for an illustration of this.

Proof of (c) one comparison per interval. Write $t=s_{j_\ell}$, and consider a vertex $x\in J_\ell$. Suppose $x\in\operatorname{Vor}(s)$, then clearly $f_x^s(t)\geq\omega(s)-\omega(t)$. On the other hand if $x\notin\operatorname{Vor}(s)$, then by (a) $x$ belongs to a rooted subtree $C_e$ of $T-\operatorname{V}(\operatorname{Vor}(s))$ with parent edge $e$. Let $v$ be the endpoint of $e$ that is the root of $C_e$. By part (b), the dual of $e$ belongs to $E_\ell$. Since $e$ separates $\operatorname{Vor}(s)$ from $\operatorname{Vor}(t)$, we must have $v\in\operatorname{Vor}(t)$. This means that $f_v^s(t)<\omega(s)-\omega(t)$. By Equation (4), it follows that:

This means $x\notin\operatorname{Vor}(s)$ fails the comparison, proving (c). □

Computing Voronoi Edge Intervals

We use a theorem of Mozes and Prigan [31] that efficiently computes a Voronoi diagram of a set $B$ of sites lying on one face. We can assume all other faces have exactly three sides without changing the underlying graph metric by adding long edges (see simplifying assumptions of § 2). The key idea is to find trichromatic triangles which are faces with three vertices belonging to different Voronoi cells. These are the dual vertices of the Voronoi diagram of degree three. The theorem is as follows.

To recover the intervals according to the CCW-first indices of the shortest path trees, we can use Lemma 11 to get the index $\rho(e)$ for trichromatic edges.

Together with the compressed Voronoi diagram and Lemma 11, we can compute the indices of the interval corresponding to each Voronoi edge.

Data Structures via Range Searching

In this section we describe standard range searching data structures to show that finding the farthest vertex can be performed using upper envelopes of distance profile pseudolines.

Lemma 12(c) says that we can decompose the Euler tour into intervals where we need to only compare distance profiles with a single competitor boundary site to determine if vertices are in $\operatorname{Vor}(s)$. This means that for interval $J_\ell$, it suffices to query $\lvert\operatorname{Vor}(s)\rvert$ many intervals for the vertex $x$ that maximizes $d_H(s,x)$ while satisfying $f_x(s_{j_\ell}) \geq\omega(s) - \omega(s_{j_\ell})$. This can be encapsulated in the following problem.

This problem can be solved using standard multilevel orthogonal range searching technique where we store the upper envelope data structures. We give here the full proof of this via reduction to a problem that can be solved using upper envelopes (in our case with Lemma 10). For this reduction, it helps to define the following intermediate problem.

We also define the following problem that can be solved using upper envelopes.

The reductions are standard. We present a full proof here for completeness.

Proof. As an intermediate step, we first reduce Problem 1 to Problem 2.

Reducing from Problem 1 to Problem 2 We proceed by standard divide and conquer. Sort all values of $d_i$, and split the pseudolines into two sets $F_{\mathrm{HIGH}}$ and $F_{\mathrm{LOW}}$ for which all values in $F_{\mathrm{HIGH}}$ are greater than those in $F_{\mathrm{LOW}}$. Build the data structure for Problem 2 on $F_{\mathrm{HIGH}}$, then recursively build a data structure for Problem 1 on both $F_{\mathrm{LOW}}$ and $F_{\mathrm{HIGH}}$. Queries can be handled by binary search, use the data structure for $F_{\mathrm{HIGH}}$ to determine if any pseudoline with $d_i$ value larger than $m$ satisfies the interval and threshold condition. If there is, then recurse on $F_{\mathrm{HIGH}}$, otherwise recurse on $F_{\mathrm{LOW}}$. In the recursion, binary search for new endpoints of the query interval, since $F_{\mathrm{LOW}}$ and $F_{\mathrm{HIGH}}$ only contain subsets of the original indices.

Suppose we had a data structure for Problem 2 with $T_2(k)$ preprocessing time with $Q_2(k)$ query time. The construction time for the data structure for Problem 1 has the recurrence $T_1(k) = T_2(k/2) + 2T_1(k/2) + O(k\log k)$. This solves to $T_1(k) = \widetilde{O}(T_2(k))$ as any data structure for $T_2(k)$ takes at least $\Omega(k)$ time. The query time has the recurrence $Q_1(k) = Q_2(k/2) + Q_1(k) + O(\log k)$, which solves to $Q_1(k) = \widetilde{O}(Q_2(k))$.

:::

Reducing from Problem 2 to Problem 3 This follows by standard segment trees [14], that decompose an interval into $O(\log k)$ dyadic intervals. Suppose we had a data structure for Problem 3 with $T_3(k)$ preprocessing time with $Q_3(k)=\widetilde{O}(1)$ query time. Then the preprocessing time satisfies $T_2(k)=2T_2(k/2)+T_3(k)$ which solves to $T_2(k)=\widetilde{O}(T_3(k))$ by building a solution to Problem 3, and ignoring the global preprocessing time. To perform a query, it takes $Q_2(k)=O(\log k)\cdot Q_3(k)$ time. Thus we have shown that $T_1(k)=\widetilde{O}(T_2(k))=\widetilde{O}(T_3(k))$ and that $Q_1(k)=\widetilde{O}(Q_2(k))=\widetilde{O}(Q_3(k))$. so we conclude the lemma.

Proving thm:mainds

Here we prove our main data structure result of Theorem 2 that we restate below for convenience.

Proof. We begin by describing the data structure.

Data structure We store the data structure of Corollary 14 for recovering Voronoi edge intervals and a single MSSP data structure from Theorem 4 shared by all boundary vertices. For each $s_i\in B$, we also store the data structure for Problem 1 on the pseudolines $\{f_x^{s_i}\}_{x\in X}$ in increasing order of $\operatorname{pre}_{i}(x)$, associating each pseudoline $f_x^{s_i}$ with the distance $d_H(s_i,x)$.

Preprocessing time Constructing the data structures for computing Voronoi edge intervals and MSSP takes $\widetilde{O}(N)$ preprocessing time. Using distances obtained by the MSSP, Lemma 10 allows for constructing an upper envelope to solve the decision problem of Problem 3 on any $k'$ pseudolines with the same boundary vertex $s_i\in B$ in $\widetilde{O}(k')$ time after $\widetilde{O}(bk)$ preprocessing. The reduction of Lemma 15 therefore gives $\widetilde{O}(k)$ construction time for the data structure for Problem 1 at each boundary vertex, or $\widetilde{O}(bk)$ over all boundary vertices. The total preprocessing time is thus $\widetilde{O}(N+bk)$.

Handling a query Given an admissible weight function $\omega$, we use Corollary 14 to construct an implicit representation of its Voronoi diagram in $\widetilde{O}(b)$ time. For each Voronoi edge on the boundary of a cell $\operatorname{Vor}(s_i)$, we recover the corresponding interval in the CCW-first ordering rooted at $s_i$ in $\widetilde{O}(1)$ time. By Lemma 12(c), processing this interval requires one query (or two for circular intervals) to the data structure for Problem 1 associated with $s_i$, also taking $\widetilde{O}(1)$ time. Thus, after constructing the diagram, we can process all boundary edges of $\operatorname{Vor}(s_i)$ in $\widetilde{O}(|\partial\operatorname{Vor}(s_i)|)$ time.

Conclusion

We have reached a milestone for planar diameter and all vertex eccentricities by showing that these quantities can be computed in $\widetilde{O}(n^{3/2})$ time. We conclude with some open problems.

1. Tighter bounds for exact planar diameter. We reiterate the question asked by Abboud, Mozes, and Weimann [1]. Does planar diameter admit an $n^{1+o(1)}$-time algorithm or can a superlinear lower bound be proved? Are other improvements beyond $\widetilde{O}(n^{3/2})$ for planar diameter possible?

2. Wiener index. The Wiener index computes the sum of shortest path distances between all pairs of vertices. Upper envelopes are only good for maximum queries, so our farthest vertex

data structure of Theorem 2 does not naturally support computation of Wiener index. Typically, supporting the Wiener index requires computation of sums and counts of vertices in a Voronoi cell. Since queries can be processed offline, it may be possible to use point-pseudoline range searching data structures to handle $q$ queries on $k$ pseudolines in $\widetilde{O}(q^{2/3}k^{2/3})$ time. Unfortunately this does not directly lead to any improvement on the $\widetilde{O}(n^{5/3})$ time algorithm in [GKM+21].

3. Dynamic exact diameter and distance oracles. Can the structural observations relating to pseudolines made in this paper help for dynamic exact distance problems?

AI Methodology

The results presented in this paper were developed through multiple interactions with GPT-6 Astra. The idea to use range searching and pseudolines was suggested by the first author. The manuscript itself was written by the authors with editing assistance by the LLM.