Faster Construction of a Planar Distance Oracle with $\stackrel{\mathbf{~}}{𝑶}\mathbf{(}\mathrm{𝟏}\mathbf{)}$ Query Time

Let $Q$ and $S$ denote the query-time and the space of an oracle, respectively. The early planar distance oracles [1, 15, 13] were based solely on planar separators [31, 33, 18] and achieved a tradeoff of $Q=\tilde{O}(n/\sqrt{S})$ for $S\in [n^{4/3},n^2]$, and $Q=O(n^2/S)$ for $S\in [n,n^{4/3})$. In [17], Fakcharoenphol and Rao introduced the use of Monge matrices to distance oracles, and devised an oracle with $\tilde{O}(n)$ space and $\tilde{O}(\sqrt{n})$ query time. By combining their ideas with Klein’s [25, 6] multiple source shortest path (MSSP) data structure, Mozes and Sommer [36] obtained the $Q=\tilde{O}(n/\sqrt{S})$ tradeoff for nearly the full range $[n\log \log n,n^2]$. Other works [40, 38, 36, 19] focused on achieving strictly optimal query-time or strictly optimal space. Namely, Wulff-Nilsen’s work [40] gives optimal $O(1)$ queries with weakly subquadratic $O(n^2{\log }^4\log n/\log n)$ space, whereas Nussbaum [38] and Mozes and Sommer’s [36] oracles give optimal $O(n)$ space with $O(n^{1/2+ϵ})$ query-time. Except for [40], all of the above oracles can be constructed in $\tilde{O}(n)$ time. However, none of them provides polylogarithmic $\tilde{O}(1)$ query-time using truly subquadratic $O(n^{2-\epsilon })$ space.

In FOCS 2017, Cohen-Addad, Dahlgaard, and Wulff-Nilsen [14] (inspired by Cabello’s [5] breakthrough use of Voronoi diagrams for computing the diameter of planar graphs) realized that Voronoi diagrams, when applied to regions of an $r$-division, can be used to break the barrier mentioned above. In particular, they presented the first oracle with $\tilde{O}(1)$ query-time and truly subquadratic $O(n^{5/3})$ space, or more generally, the tradeoff $Q=\tilde{O}(n^{5/2}/S^{3/2})$ for any $S\in [n^{3/2},n^{5/3}]$. This came at the cost of increasing the preprocessing time from $\tilde{O}(n)$ to $O(n^2)$, which was subsequently improved to match the space bound [20]. In SODA 2018, Gawrychowski, Mozes, Weimann, and Wulff-Nilsen [21] improved the space and preprocessing time to $\tilde{O}(n^{3/2})$ with $\tilde{O}(1)$ query-time (and the tradeoff to $Q=\tilde{O}(n^{3/2}/S)$ for $S\in [n,n^{3/2}]$) by defining a dual representation of Voronoi diagrams and developing an efficient point-location mechanism on top of it. In STOC 2019, Charalampopoulos, Gawrychowski, Mozes, and Weimann [10] observed that the same point-location mechanism can be used on the Voronoi diagram for the complement of regions in the $r$-division. This observation alone suffices to improve the oracle size to $O(n^{4/3})$ (while maintaining $\tilde{O}(1)$ query-time). By combining this with a sophisticated recursion (where a query at recursion level $i$ reduces to $\log n$ queries at level $i+1$) they further obtained an oracle of size $n^{1+o(1)}$ and query-time $n^{o(1)}$. Finally, in SODA 2021, Long and Pettie [32] showed how much of the point-location work can be done without recursion, and that only two (rather than $\log n$) recursive calls suffice. This led to the state of the art oracle, requiring $n^{1+o(1)}$ space and $\tilde{O}(1)$ query-time or $\tilde{O}(n)$ space and $n^{o(1)}$ query-time.¹¹1A journal version containing all the above Voronoi-based oracles was published in JACM in 2023 [9].

In terms of space and query time, these latter Voronoi-based oracles are almost optimal. However, their construction time is $\tilde{O}(n^{3/2})$, and improving it is mentioned in [9] as an important open problem. The bottleneck behind this $\tilde{O}(n^{3/2})$ bound is the time for constructing Voronoi diagrams as we next explain.

Let $X$ be a planar graph, and let $f$ be a face of $X$. The vertices of $f$ are called the sites of the Voronoi diagram, and each site $s$ has a weight $\omega (s)\ge 0$ associated with it. The distance between a site $s$ and a vertex $v\in X$, denoted by ${\mathrm{𝖽𝗂𝗌𝗍}}^{\omega }(s,v)$ is defined as $\omega (s)$ plus the length of the $s$-to-$v$ shortest path in $X$. The additively weighted Voronoi diagram $\text{VD}(f,\omega )$ is a partition of $X$’s vertices into pairwise disjoint sets, one set $\text{Vor}(s)$ for each site $s$. The set $\text{Vor}(s)$, called the Voronoi cell of $s$, contains all vertices in $X$ that are closer (w.r.t. ${\mathrm{𝖽𝗂𝗌𝗍}}^{\omega }(\cdot ,\cdot )$) to $s$ than to any other site (we assume that distances are unique to avoid the need to handle ties²²2This assumption can be achieved in $O(n)$ time. With high probability using [34, 37], or deterministically using [16].). A point-location query $v$ asks for the site $s$ whose Voronoi cell $\text{Vor}(s)$ contains $v$. There exists a dual representation ${\text{VD}}^{\ast }(f,\omega )$ of $\text{VD}(f,\omega )$. The size of this representation is $O(|f|)$, and together with an MSSP data structure it supports point-location queries in $\tilde{O}(1)$ time.

In [9], it was shown that given the MSSP of a graph (piece) $X$, a face $f$ of $X$, and additive weights $\omega (\cdot )$ to the vertices of $f$, the Voronoi diagram ${\text{VD}}^{\ast }(f,\omega )$ can be constructed in $\tilde{O}(\sqrt{n|f|})$ time. In this paper, we show (see Theorem 15) how to construct it in near-optimal $\tilde{O}(|f|)$ time when the graph is undirected. As discussed below, this leads to a static distance oracle of space $\tilde{O}(n^{4/3})$, construction time $\tilde{O}(n^{4/3})$, and query-time $\tilde{O}(1)$. In addition, it implies a dynamic distance oracle that supports $\tilde{O}(1)$-time distance queries from a single-source $s$, and $\tilde{O}(n^{2/3})$-time updates consisting of edge insertions, edge deletions, and changing the source $s$. The dynamic distance oracle is obtained by simply plugging our construction into the oracle of Charalampopoulos and Karczmarz [12] (thus improving its update time from $\tilde{O}(n^{4/5})$ to $\tilde{O}(n^{2/3})$). We note that the current best all-pairs dynamic oracle by Fakcharoenphol and Rao [17] has $\tilde{O}(n^{2/3})$ update time and $\tilde{O}(n^{2/3})$ query time. Therefore, in undirected graphs, our new oracle achieves the same bounds but has the benefit that, between source changes, the query takes only $\tilde{O}(1)$ time.

Our construction is inspired by Charalampopoulos, Gawrychowski, Mozes, and Weimann who showed in ICALP 2021 [11] that near-optimal $\tilde{O}(|f|)$ construction time is possible for the special case when the planar graph is an alignment graph of two strings. The alignment graph is an acyclic grid graph of constant degree. More importantly, shortest paths in this graph are monotone, in the sense that they only go right or down along the grid. This makes the Voronoi diagram of every piece $X$ much more structured. In particular, one can find the trichromatic vertices of ${\text{VD}}^{\ast }$ (i.e., the faces of $X$ whose vertices belong to three different Voronoi cells) by recursively zooming in on them using cycle separators; The intersection of a cycle separator with each Voronoi cell consists of at most two contiguous intervals of the cycle separator. This partition induced by these intervals can be found with a binary search approach, whose complexity (up to a logarithmic factor) is linear in the number of trichromatic vertices enclosed by the cycle. From the partition it is easy to deduce whether a trichromatic vertex of ${\text{VD}}^{\ast }$ is enclosed by the cycle separator, and infer whether we should recurse on each side of the separator. In this paper we extend this binary search approach to general undirected planar graphs.

At a first glance, such an extension seems impossible as the intersection of cycle separators and Voronoi cells might be very fragmented, even when there are only three sites. To overcome this, we use shortest path separators. Such separators have been widely used in essentially all approximate distance oracles for planar graphs, but also in exact algorithms (e.g., [7, 3, 28, 35]). These cycle separators may contain $\mathrm{\Theta }(n)$ edges (rather than $O(\sqrt{n})$), but consist of two shortest paths $P,P^{\prime }$, so that, because the graph is undirected, any other shortest path can intersect each of $P,P^{\prime }$ at most once. In our context, this implies a monotonicity property when we restrict our attention to shortest paths that enter the cycle separator only from the left or only from the right. If we only allow paths to enter $P$ from one side, say the left, then the intersection of each Voronoi cell (with distances now defined under this restriction) with $P$ is a single contiguous interval.

To better explain the difficulties with this approach and how we overcome them, let us first define some terminology. We say that vertex $v\in P$ prefers a site $s$ if $v$ belongs to $\text{Vor}(s)$ (defined without any restrictions). We say that $v\in P$ left-prefers a site $s$ if $v$ belongs to $\text{Vor}(s)$ under the restriction that paths are only allowed to enter $P$ from the left. Repeating the above discussion using this terminology, the partition induced by the prefers relation may be very fragmented, but the partition induced by the left-prefers relation is not fragmented. There are two immediate problems with working with the partition induced by left-preference (or right-preference). First, we are interested in constructing the Voronoi diagram without any restrictions, and second, we do not know how to efficiently compute shortest paths under restrictions on the direction in which they enter $P$.

To address the first difficulty we show that one can infer which sides of the cycle separator contain a trichromatic vertex of the Voronoi diagram (without restrictions) by inspecting the endpoints of the intervals of the two partitions - the one with respect to left-preference and the one with respect to right-preference. This is shown in Section 4. We also show, by adapting the divide-and-conquer construction algorithm of [20], how to reduce the problem of computing a Voronoi diagram with many sites to the problem of computing the trichromatic vertex of a Voronoi diagram with only three sites. This is explained in Section 5.

Overcoming the second difficulty is the heart of our technical contribution. We know how to efficiently determine, by enhancing the standard MSSP data structure, whether the true shortest path from a site $s$ to a vertex $v\in P$ enters $P$ from the right or from the left. However, we do not know how to efficiently report the shortest path from $s$ to $v$ that enters $P$ from the other side (because that path is not the overall shortest path from $s$ to $v$). We observe that we can work with relaxed preferences. If $v$ prefers $s$ (without restrictions on left/right), then: (1) we might as well say that $v$ both right-prefers and left-prefers $s$ (because either way this will point us to $s$), and (2) if the shortest path from $s$ to $v$ enters $P$ from the right, we do not really care what the left preference of $v$ is, so we might as well say that $v$ left-prefers $s^{\prime }$ for any site $s^{\prime }$. In Section 3 we describe how to compute a partition with respect to such a relaxed notion of left-preference and right-preference. The exact details are a bit more complicated than described here. In particular we use the term like rather than prefer to express that the preference is more loose.

Constructing a partition with relaxed preferences turns out to be more complicated than with strict preferences. One challenge comes from the fact that with relaxed preferences making progress in a binary search procedure is problematic. This is because a vertex $v$ of $P$ no longer has a unique left-preferred site $s$. In fact, when working with relaxed preferences, a vertex $v$ may equally like all sites. Thus, we need to have some way to recognize a “winner” site with respect to a vertex that does not have a unique preference. Another challenge we encounter is what we call swirly paths - when the $s$-to-$v$ path goes around $P$ before entering $P$. Swirly paths make the realizations of many of the arguments outlined here more complicated. The structure of the shortest paths that allows us to make progress in the binary search procedure is different and more complicated in the presence of swirly paths. Moreover, we do not always know how to efficiently identify whether a shortest path is swirly or not. To simplify the presentation we first explain how to obtain a partition with respect to relaxed preferences when there are no swirly paths. In the full version of the paper [2] we describe how to handle swirly paths.

We believe that our result is a promising step toward exact oracles that simultaneously have optimal space, query-time and preprocessing time. One way to achieve this would be to be able to find a way to use recursion to obtain the functionality of our enhanced MSSP data structure without actually computing it over and over in large regions of the graph, in a similar manner to the way this issue was avoided for the standard MSSP in [9]). This seems to be the only significant obstacle preventing us from pushing our new ideas all the way through, and obtaining an almost optimal $n^{1+o(1)}$ construction time for undirected planar graphs.

With a standard transformation (without increasing the size of $G$ asymptotically) we can guarantee that each vertex of $G$ has constant degree and that $G$ is triangulated. Consider a subgraph $X$ (called a piece) of $G$ whose boundary vertices $\partial X$ (vertices incident to edges in $G\setminus X$) lie on a single face $f$ of $X$. Note that $f$ is the only face of $X$ that is not a triangle. The vertices of $f$, assigned with weights $\omega (\cdot )$, are the sites of the Voronoi diagram $\text{VD}=\text{VD}(f,\omega )$ of $X$. There is a dual representation ${\text{VD}}^{\ast }$ of VD as a tree with $O(|f|)$ vertices (see Figure 1): Let $X^{\ast }$ be the planar dual of $X$. Consider the subgraph of $X^{\ast }$ consisting of the duals of edges $uv$ of $X$ such that $u$ and $v$ are in different Voronoi cells. In this subgraph, we repeatedly contract edges incident to degree-2 vertices. The remaining vertices (edges) are called Voronoi vertices (edges). A Voronoi vertex is dual to a face whose three vertices belong to three different Voronoi cells. We call such a face (and its corresponding dual vertex) trichromatic. Finally, we define ${\text{VD}}^{\ast }$ to be the tree obtained from the subgraph by replacing the node $f^{\ast }$ by multiple copies, one for each edge incident to $f^{\ast }$. The complexity (i.e., the number of vertices and edges) of ${\text{VD}}^{\ast }$ is $O(|f|)$. For example, in a VD of just two sites $s$ and $t$, there are no trichromatic faces. In this case, ${\text{VD}}^{\ast }$ is just a single edge corresponding to an $st$-cut or equivalently to a cycle in the dual graph. We call this cycle the $st$-bisector and denote it by ${\beta }^{\ast }(s,t)$. Note that a trichromatic vertex is a meeting point of three bisectors. Another important example is a VD of three sites (we call this a trichromatic VD). Such a VD has at most one trichromatic face (in addition to face $f$ itself).

To see why point-location on Voronoi diagrams is useful for distance oracles, we describe here the $\tilde{O}(n^{4/3})$-space $\tilde{O}(1)$-query oracle of [10] that we will be using. It begins with an $r$-division of the graph $G$. This is a partition of $G$ into $O(n/r)$ subgraphs (called pieces) such that every piece $X$ contains $O(r)$ vertices and $O(\sqrt{r})$ boundary vertices $\partial X$ (vertices shared by more than one piece). An $r$-division can be computed in $\tilde{O}(n)$ time [27] with the additional property that the boundary vertices $\partial X$ of every piece $X$ lie on a constant number of faces of the piece (called holes). To simplify the presentation, we assume that $\partial X$ lies on a single hole (in general, we apply the same reasoning to each hole separately, and return the minimum distance found among the $O(1)$ holes). The oracle consists of the following for each piece $X$ of the $r$-division:

1. 1.

   The $O({|X|}^{3/2})$ space, $O({|X|}^{3/2})$ construction time, $\tilde{O}(1)$ query-time distance oracle of [21] on the graph $X$. In total, these require $O(n\sqrt{r})$ space and construction time.

2. 2.

   Two MSSP data structures [25], one for $X$ and one for $X^{out}=G\setminus (X\setminus \partial X)$, both with sources $\partial X$. The MSSP for $X$ requires space $O(r\log r)$, and the MSSP for $X^{out}$ requires space $O(n\log n)$. Using these MSSPs, we can then query in $\tilde{O}(1)$ time the $u$-to-$v$ distance for any $u\in \partial X$ and $v\in G$. The total space and construction time of these MSSPs is $\tilde{O}(n^2/r)$, since there are $O(n/r)$ pieces.

3. 3.

   For each vertex $u$ of $X$, compute the Voronoi diagram ${\text{VD}}_{in}(u,X)$ (resp. ${\text{VD}}_{out}(u,X)$) for $X$ (resp. $X^{out}$) with sites $\partial X$ and additive weights the distances from $u$ to these vertices in $G$ (the additive weights are computed in $\tilde{O}(|\partial X|)=\tilde{O}(\sqrt{r})$ time using [17]). Each Voronoi diagram can be represented in $O(\sqrt{r})$ space [21] and can be constructed in $\tilde{O}(\sqrt{n\sqrt{r}})$ time [10]. Hence, all Voronoi diagrams require $O(n\sqrt{r})$ space and $\tilde{O}(n^{3/2}{r}^{1/4})$ construction time.

To query a $u$-to-$v$ distance, let $X$ be the piece that contains $u$. If $v\notin X$ then the $u$-to-$v$ path must cross $\partial X$. We perform a point-location query for $v$ in ${\text{VD}}_{out}(u,X)$ in time $\tilde{O}(1)$ [21]. If $v\in \text{Vor}(s)$ then we return the $u$-to-$s$ distance (from the precomputed additive weight) plus the $s$-to-$v$ distance (from the MSSP of $X^{out}$). Otherwise, $v\in X$ and we return the minimum of two options: (1) The shortest $u$-to-$v$ path crosses $\partial X$. This is similar to the previous case except that the point-location query for $v$ is done in ${\text{VD}}_{in}(u,X)$. (2) The shortest $u$-to-$v$ path does not cross $\partial X$ (i.e., the path lies entirely within $X$). We retrieve this distance by querying the distance oracle stored for $X$.

By choosing $r=n^{2/3}$ we get an oracle of space $\tilde{O}(n^{4/3})$ and query-time $\tilde{O}(1)$. The construction time however is $\tilde{O}(n^{5/3})$. Notice that the only bottleneck preventing $\tilde{O}(n^{4/3})$ construction time is the construction of the Voronoi diagrams.

A shortest path separator $Q$ is a balanced cycle separator consisting of two shortest paths $P$ and $P^{\prime }$ (emanating at the same vertex) plus a single edge. A complete recursive decomposition tree $T$ of $G$ using shortest path separators can be obtained in linear time [30].

An arc $e=uv$ emanates (enters) left of a simple path $P$ if there exist two arcs $e_1$, $e_2$ in $P$, such that $u$ ($v$) is the head of $e_1$ and the tail of $e_2$, and $e$ appears between $e_1$ and $e_2$ in the clockwise order of arcs incident to $u$. Otherwise, $e$ emanates (enters) right of $P$. Notice that this is not defined for the endpoints of $P$, however, in the context in which we will use it, we will always extend $P$ so that its original endpoints will become internal. Specifically, consider a shortest path separator $Q$ composed of an $x$-to-$y$ path $P$, an $x$-to-$y^{\prime }$ path $P^{\prime }$, and an edge $(y,y^{\prime })$. Then, we will extend $P$ on one side with $y^{\prime }$ and on the other side with the vertex following $x$ on $P^{\prime }$. A symmetric extension will be done for $P^{\prime }$.