An $𝑶\mathbf{(}𝒏\mathrm{𝐥𝐨𝐠}𝒏\mathbf{)}$ Algorithm for Single-Source Shortest Paths in Disk Graphs

Our main result in this paper is an algorithm for the SSSP problem in disk graphs that runs in $O(n\log n)$ expected time. We obtain this result using a version of the framework proposed by Klost [21]; our specialized framework and its relation to Klost’s framework are discussed in detail in Section 2. A core ingredient in the framework is a clique-based contraction of the intersection graph ${𝒢}^{\times }[𝒟]$: a graph obtained from ${𝒢}^{\times }[𝒟]$ by contracting certain cliques to single nodes. To compute such a clique-based contraction in $O(n\log n)$ time, we combine shifted quadtrees [5] and skip quadtrees [15] – powerful and beautiful concepts that we believe deserve more attention – with standard techniques for stabbing fat objects.

Our algorithm for computing a clique-based contraction not only applies to disk graphs but also to intersection graphs of fat triangles, that is, triangles all of whose internal angles are lower bounded by a fixed constant $\alpha >0$ [2]. By combining this with a novel intersecting-detection data structure for fat triangles, we obtain an $O(n{\log }^{3}n)$ algorithm for the SSSP problem on intersection graphs of fat triangles. We are not aware of previous work on the SSSP problem for fat triangles. The all-pairs shortest-path (APSP) problem, however, has been considered for fat triangles, by Chan and Skrepetos [9]. The algorithm they present runs in $O(n^2{\log }^{4}n)$ time, under the condition that the fat triangles have roughly the same size. (They also present an $O(n^2\log n)$ algorithm for the APSP problem for arbitrary disk graphs, and an $O(n^2)$ algorithm for unit-disk graphs [8].) Running our new SSSP algorithm $n$ times, once for each input triangle as the source, we obtain an APSP algorithm for arbitrarily-sized fat triangles that runs in $O(n^2{\log }^{3}n)$ time. This is faster and more general than the algorithm of Chan and Skrepetos. (The improvement for the APSP problem is mainly because of our new intersection-detection data structure for fat triangles; using this data structures in the existing algorithm [9] would also give an $O(n^2{\log }^{3}n)$ algorithm.)

In the full version of this work [11] we provide two enhancements: we obtain a deterministic $O(n\log n)$ algorithm for the SSSP problem in disk graphs and we reduce the running time for the SSSP problem on intersection graphs of fat triangles to $O(n{\log }^{2}n)$. The basic structure of the algorithms is the same as here, but we improve some of the subroutines that we use.

We use the real-RAM model – this is the standard model in computational geometry, which allows us for example to check in $O(1)$ time if two disks intersect – extended with an additional operation that allows us to compute a compressed quadtree on a set of $n$ points in $O(n\log n)$ time. This extension is common when working with quadtrees; see the book by Har-Peled [19].

It is straightforward to prove by induction on $\mathrm{\ell }$ that our algorithm correctly computes the levels $L_{\mathrm{\ell }}$ of the shortest-path tree. To prove the bound on the running time, observe that Steps 1–3 take $O(T_{\mathrm{ccg}}(n))$ time. It remains to bound the runtime of the while-loop.

For a clique $C\in 𝒞$, let $\mathrm{dist}[C]:={\min }_{D\in C}\mathrm{dist}[D]$. Note that for objects $D,D^{\prime }$ in cliques $C,C^{\prime }\in 𝒞$ that are neighbors in $\mathscr{H}$, we have $|\mathrm{dist}[D]-\mathrm{dist}[D^{\prime }]|⩽3$. Hence, $D$ can only be in the candidate set ${𝒟}_{\mathrm{cand}}$ in iterations of the while-loop where $\mathrm{dist}[D]-3⩽\mathrm{\ell }⩽\mathrm{dist}[C]-1$. Thus, if we denote the size of ${𝒟}_{\mathrm{cand}}$ in iteration $\mathrm{\ell }$ by $n_{\mathrm{\ell }}$, then the total time needed for Step 6 over all iterations is ${\sum }_{\mathrm{\ell }}{T}_{\mathrm{bit}}(n_{\mathrm{\ell }},|L_{\mathrm{\ell }}|)$, where ${\sum }_{\mathrm{\ell }}{n}_{\mathrm{\ell }}⩽3n$ and ${\sum }_{\mathrm{\ell }}|L_{\mathrm{\ell }}|⩽n$. Since $T_{\mathrm{bit}}(n_B,n_R)$ is at least linear in $n_B$ and $n_R$ (and at most quadratic), we have ${\sum }_{\mathrm{\ell }}{T}_{\mathrm{bit}}(n_{\mathrm{\ell }},|L_{\mathrm{\ell }}|)=O(T_{\mathrm{bit}}(n,n))$. This also bounds the total runtime of Steps 7–11 over all iterations.

To bound the total time for Step 5, note that a clique $C$ is only considered in iterations where $\mathrm{dist}[C]-2⩽\mathrm{\ell }⩽\mathrm{dist}[C]+2$. This implies that the total time to find the relevant cliques in Step 5 is $O(|E_{\mathscr{H}}|)$. The total time to inspect those cliques in order to find the candidate sets, is $O({\sum }_{C\in 𝒞}|C|)$. Thus, the total time for Step 5 over all iterations is $O(|E_{\mathscr{H}}|+{\sum }_{C\in 𝒞}|C|)$, which can be bounded by $O(T_{\mathrm{ccg}}(n))$. $◀$

Our algorithm to create the set of cliques is related to a recent construction by Chan and Huang [7, Section 3] of 3-hop spanners for disk graphs; we comment more on the similarities and differences later. The construction is based on so-called shifted quadtrees, introduced by Chan [5], which we describe next.

We start by defining hierarchical grids, a concept closely related to quadtrees; the connection will be made clear below. Let $o=(o_x,o_y)$ be any point in the plane. A cell in the hierarchical grid centered at $o$ is any square of the form

for integers $i,j,\mathrm{\ell }\in \mathbb{Z}$. Note that $\sigma (o,\mathrm{\ell },i,j)$ is a translation of the square $[0,2^{\mathrm{\ell }})\times [0,2^{\mathrm{\ell }})$ by the vector $o+(i\cdot 2^{\mathrm{\ell }},j\cdot 2^{\mathrm{\ell }})$, and that the set $\mathrm{\Sigma }(o,\mathrm{\ell }):=\{\sigma (o,\mathrm{\ell },i,j):i,j\in \mathbb{Z}\}$ forms a regular grid. Moreover, the grid $\mathrm{\Sigma }(o,\mathrm{\ell }-1)$ is a refinement of the grid $\mathrm{\Sigma }(o,\mathrm{\ell })$, obtained by partitioning each cell of $\mathrm{\Sigma }(o,\mathrm{\ell })$ into four quadrants. We define the hierarchical grid centered at $o$, denoted by $\mathrm{\Gamma }(o)$, to be the (infinite) collection $\{\mathrm{\Sigma }(o,\mathrm{\ell }):\mathrm{\ell }\in \mathbb{Z}\}$ of nested grids.

Define the size of any object $D$, denoted by $\mathrm{size}(D)$, to be the side length of a smallest enclosing (axis-parallel) square of $D$. Thus $\mathrm{size}(\sigma )=2^{\mathrm{\ell }}$ for any cell $\sigma \in \mathrm{\Sigma }(o,\mathrm{\ell })$. We say that an object $D$ is $c$-aligned with a hierarchical grid $\mathrm{\Gamma }$, for a given constant $c>0$, if there exists a cell $\sigma$ in $\mathrm{\Gamma }$ such that $D\subset \sigma$ and $\mathrm{size}(\sigma )⩽c\cdot \mathrm{size}(D)$. Note that whether or not $D$ is $c$-aligned with $\mathrm{\Gamma }$ only depends on the choice of the center $o$ of the hierarchical grid. The definition of being $c$-aligned trivially implies the following.

Let $𝒟$ be a finite set of objects. In general, it is impossible to choose the center of a hierarchical grid $\mathrm{\Gamma }$ such that each object $D\in 𝒟$ is $c$-aligned with $\mathrm{\Gamma }$. However, Chan [5] has shown that, surprisingly, it is possible to pick a small number of different centers such that each object $D\in 𝒟$ is $c$-aligned with at least one of the resulting hierarchical grids, for a suitable constant $c$. Even more surprisingly, we can select these centers independently of $𝒟$. The following lemma follows directly from Lemma 3.2 in Chan’s paper.³³3Chan uses the term shifted quadtree in his lemma. To stress the fact that the shifts are independent of any input set on which one might build a quadtree, we prefer to use the term hierarchical grid.

Let $P$ be a set of points, let $\mathrm{\Gamma }$ be a hierarchical grid centered at a given center $o$, and let ${\sigma }_0$ be a cell of $\mathrm{\Gamma }$ that contains $P$. Then we can construct a quadtree on $P$ – see Figure 2(i) – whose root node corresponds to ${\sigma }_0$. Any node in this quadtree corresponds to a cell of $\mathrm{\Gamma }$. Let $𝒬=𝒬({\sigma }_0,P)$ be the corresponding compressed quadtree [19]. Each internal node $\nu$ of $𝒬$ corresponds to a cell ${\sigma }_{\nu }$ of $\mathrm{\Gamma }$ and each leaf node $\mu$ corresponds to a region ${\sigma }_{\mu }$ that is either a cell of $\mathrm{\Gamma }$ or a donut cell; see Figure 2(ii). (A donut cell is the difference ${\sigma }_1\setminus {\sigma }_2$ of two cells ${\sigma }_1$ and ${\sigma }_2$ of $\mathrm{\Gamma }$ with ${\sigma }_2\subset {\sigma }_1$.) The subdivision defined by the compressed quadtree $𝒬$ is the set of regions corresponding to the leaves of $𝒬$; this subdivision is a decomposition of ${\sigma }_0$.

Our algorithm to efficiently compute the cliques in the clique-based contraction combines the hierarchical grids of Lemma 3 with skip quadtrees [15], as explained next.

Skip quadtrees, defined by Eppstein, Goodrich, and Sun [15] are defined as follows. Let $P$ be a set of $n$ points inside a given starting cell ${\sigma }_0$ of a hierarchical grid $\mathrm{\Gamma }$. We start by sorting the points in $P$ in Z-order, as follows. First, order the points according to the quadrants from ${\sigma }_0$ they fall in: put the points in the nw-quadrant first, then those in the ne-quadrant, then those in the sw-quadrant, and finally those in the se-quadrant. Next, recursively sort the points in each quadrant. Let $p_1,\mathrm{\dots },p_n$ be the resulting sorted list of points; see Figure 2(iii). We now create a sequence $P=P_0\supset P_1\supset \mathrm{\cdots }\supset P_t$, where $P_i$ is obtained from $P_{i-1}$ by deleting every other element (starting with the first element) and $|P_t|=1$. From the sequence $P_0\supset P_1\supset \mathrm{\cdots }\supset P_t$ we construct a sequence of compressed-quadtree subdivisions ${𝒬}_0,{𝒬}_1,\mathrm{\dots },{𝒬}_t$, each based on the same starting cell ${\sigma }_0$. The sequence ${𝒬}_0,{𝒬}_1,\mathrm{\dots },{𝒬}_t$ has the following properties, as illustrated in Figure 3:

• $\mathrm{■}$

  ${𝒬}_t$ is equal to the square ${\sigma }_0$.

• $\mathrm{■}$

  ${𝒬}_i$ is a refinement of ${𝒬}_{i+1}$ for all , that is, each region in ${𝒬}_i$ is contained in a unique region in ${𝒬}_{i+1}$. Moreover, each region in ${𝒬}_{i+1}$ contains $O(1)$ regions from ${𝒬}_i$.

• $\mathrm{■}$

  Each region in ${𝒬}_0$ contains at most one point from $P$.

We can view ${𝒬}_t,\mathrm{\dots },{𝒬}_1,{𝒬}_0$ as the levels of a tree $𝒯$, where a node $\nu$ at level $i$ corresponds to a region $R_{\nu }$ of the subdivision ${𝒬}_i$. In particular, the root of $𝒯$ corresponds to the starting square ${\sigma }_0$ and the leaves of $𝒯$ correspond to the regions in ${𝒬}_0$ (which is the compressed-quadtree subdivision for the whole point set $P$ with root ${\sigma }_0$). We call this tree structure⁴⁴4The skip quadtree defined by Eppstein, Goodrich, and Sun is slightly more complicated, as it stores more information than just the compressed-quadtree subdivisions. Since we do not need our structure to be dynamic, the simple hierarchy described above suffices. a skip quadtree for $P$ with root ${\sigma }_0$. It can be constructed in $O(n\log n)$ time [15].

Without loss of generality, we will assume henceforth that all the disks of $𝒟$ are fully contained in the unit square $[0,1)\times [0,1)$. Let $\mathrm{\Xi }$ be the collection of three hierarchical grids given by Lemma 3. Each disk $D$ of $𝒟$ is $6$-aligned with some hierarchical grid $\mathrm{\Gamma }\in \mathrm{\Xi }$, and we can find such a hierarchical grid for $D$ in constant time.

Now consider a hierarchical grid $\mathrm{\Gamma }$ from the collection $\mathrm{\Xi }$. Let $𝒟(\mathrm{\Gamma })\subset 𝒟$ be the set of disks that are 6-aligned with $\mathrm{\Gamma }$, where we put a disk that is 6-aligned with multiple grids into an arbitrary one of the corresponding sets $𝒟(\mathrm{\Gamma })$. We create a set $𝒞(\mathrm{\Gamma })$ of cliques, as follows.

1. 1.

   Construct a skip quadtree $𝒯(\mathrm{\Gamma })$ on the set $P(\mathrm{\Gamma })$ of centers of the disks in $𝒟(\mathrm{\Gamma })$, where the starting square ${\sigma }_0$ of the skip quadtree is a cell of $\mathrm{\Gamma }$ that contains all the disks in $𝒟(\mathrm{\Gamma })$.

2. 2.

   For each disk $D\in 𝒟(\mathrm{\Gamma })$, follow a path in $𝒯(\mathrm{\Gamma })$ consisting of nodes $\mu$ whose region $R_{\mu }$ contains the center of $D$, until a node $\nu$ is reached such that $D$ intersects $\partial R_{\nu }$ or a leaf is reached. Assign $D$ to that node or leaf.

3. 3.

   Let ${𝒟}_{\nu }\subset 𝒟(\mathrm{\Gamma })$ be the set of disks assigned to an (internal or leaf) node $\nu$ in $𝒯(\mathrm{\Gamma })$. For each node $\nu$, partition ${𝒟}_{\nu }$ into a set ${𝒞}_{\nu }$ of $O(1)$ cliques, as follows. If $\nu$ is a leaf and $R_{\nu }$ contains a disk – note that a leaf can contain at most one disk – then we create a singleton clique for that disk. Now suppose $\nu$ is an internal node. First, suppose $R_{\nu }$ is a square region. Because the disks in ${𝒟}_{\nu }$ are 6-aligned with $\mathrm{\Gamma }$, we know that $\mathrm{size}(D)⩾\frac{1}{6}\cdot \mathrm{size}(R_{\nu })$ for all $D\in {𝒟}_{\nu }$ intersecting $\partial R_{\nu }$. Hence, we can create a set of $O(1)$ points such that each disk $D$ is stabbed by at least one of them, which we use to create ${𝒞}_{\nu }$. If $R_{\nu }$ is a donut we proceed similarly, where we treat the disks intersecting the boundary of the hole of the donut – this hole can be much smaller than the donut – separately from the disks that only intersect the outer boundary of the donut. Finally, set $𝒞(\mathrm{\Gamma }):={\bigcup }_{\nu \in 𝒯(\mathrm{\Gamma })}{𝒞}_{\nu }$.

Each clique that is generated by our algorithm is a so-called stabbed clique, that is, for each clique $C\in 𝒞(\mathrm{\Gamma })$ there is a point stabbing all disks in $C$. We refer to the union of all the disks in $C$ as a flower, which we denote by $F(C)$, and we let $ℱ(\mathrm{\Gamma }):=\{F(C):C\in 𝒞(\mathrm{\Gamma })\}$ be the set of flowers corresponding to the cliques in $𝒞(\mathrm{\Gamma })$. Define $\mathrm{ply}(S)$, the ply of a set $S$ of objects in the plane, to be the maximum, over all points $q\in {ℝ}^2$, of the number of objects in $S$ containing $q$. The following lemma states a property of our algorithm that will be crucial to efficiently compute the edges in the clique-based contraction.

Step 1 of the algorithm, constructing the skip quadtree $𝒯(\mathrm{\Gamma })$ on the set $P(\mathrm{\Gamma })$ of the centers of the at most $n$ disks in $𝒟(\mathrm{\Gamma })$, can be done in $O(n\log n)$ time [15]. The depth of the skip quadtree is $O(\log n)$, and so Step 2 takes $O(\log n)$ time per disk and $O(n\log n)$ time in total. Step 3 takes ${\sum }_{v\in 𝒯(\mathrm{\Gamma })}O(1+|{𝒟}_v|)$ time, which is $O(n)$ because each disk is assigned to exactly one node. Hence, the total time for the algorithm is $O(n\log n)$.

To bound $\mathrm{ply}(ℱ(\mathrm{\Gamma }))$, consider an arbitrary point $q\in {ℝ}^2$. Recall that for each node $\nu$ in $𝒯(\mathrm{\Gamma })$ we created $O(1)$ stabbed cliques and, hence, $O(1)$ flowers. Thus, it suffices to prove the following claim: at each level of the skip quadtree $𝒯(\mathrm{\Gamma })$ there are only $O(1)$ nodes $\nu$ such that $q\in D$ for some disk $D$ assigned to $\nu$. To prove this claim, follow the search path of $q$ in $𝒯(\mathrm{\Gamma })$, that is, the path consisting of nodes $\mu$ such that $q\in R_{\mu }$. Let $D\in 𝒟$ be a disk that contains $q$, let $\nu$ be the node to which $D$ is assigned, and let $\mu$ be the parent of $\nu$. Then $\mu$ must lie on the search path of $q$. Indeed, $D$ is fully contained in $R_{\mu }$ – otherwise $D$ would have been assigned to $\mu$ – and so $q\in D\subset R_{\mu }$. Since any node in a skip quadtree has $O(1)$ children, this implies the claim. $◀$

Let $𝒞:={\bigcup }_{\mathrm{\Gamma }\in \mathrm{\Xi }}𝒞(\mathrm{\Gamma })$ be the set of cliques generated by applying the procedure above to each hierarchical grid $\mathrm{\Gamma }$ in the collection $\mathrm{\Xi }$ given by Lemma 3. Let $ℱ:={\bigcup }_{\mathrm{\Gamma }\in \mathrm{\Xi }}ℱ(\mathrm{\Gamma })$ be the corresponding flower set. Note that $\mathrm{ply}(ℱ)=O(\log n)$ by Lemma 3. To construct the edge set $E_{\mathscr{H}}$ of the clique-based contraction $\mathscr{H}=(𝒞,E_{\mathscr{H}})$, we must find all pairs $F,F^{\prime }\in ℱ$ that intersect. Next we show how to do this in $O(n\log n)$ time.

Consider a flower $F$ defined by some clique $C$. The boundary $\partial F$ of $F$ is comprised of maximal pieces of the boundaries of the disks in $C$ that show up on $\partial F$. We call these pieces boundary arcs and we denote the set of boundary arcs of a flower $F$ by $ℬ(F)$. For a set $ℱ$ of flowers, we define $ℬ(ℱ):={\bigcup }_{F\in ℱ}ℬ(F)$ to be the set of boundary arcs of the flowers in $ℱ$.

First, observe that $|ℬ(F)|=O(n_F)$, where $n_F$ is the number of disks defining a flower $F\in ℱ$, since the union of a set of disks has linear complexity. Hence, $|B(ℱ)|=O(n)$.

Now consider a boundary arc $\beta \in ℬ(F)$ of some flower $F\in ℱ$. We assume for simplicity that the angle spanned by the circular arc $\beta$ is at most $\pi /2$; if this is not the case we can split $\beta$ into at most four sub-arcs, and work with the sub-arcs instead. Let $D$ be the disk that contributes the arc $\beta$, let $c$ be the center of $D$, and let $s_1$ and $s_2$ be the segments that connect $c$ to the endpoints of $\beta$. Together with $\beta$, these two segments bound a (convex) circular sector. Let $Z_F$ be the set of such circular sectors created for the arcs in $ℬ(F)$; see Figure 4(i).

We say that two sectors $z,z^{\prime }$ are non-overlapping if their interiors are disjoint.

Consider two sectors $z,z^{\prime }\in Z_F$. Let $D,D^{\prime }$ be the disks whose boundaries define $z$ and $z^{\prime }$, respectively, and let $c$ and $c^{\prime }$ be their centers. If $D=D^{\prime }$ then obviously $z$ and $z^{\prime }$ do not overlap, so assume that $D\ne D^{\prime }$. Since a sector in $Z_F$ cannot be fully contained in another sector in $Z_F$ by construction, the sectors $z,z^{\prime }$ can only overlap if there is a proper intersection between their boundaries. Such an intersection can only happen between a segment $s$ connecting $c$ to an endpoint $p$ of some boundary arc $\beta \subset \partial D$ and a segment $s^{\prime }$ connecting $c^{\prime }$ to an endpoint $p^{\prime }$ of some boundary arc ${\beta }^{\prime }\subset \partial D^{\prime }$. But then, by the triangular inequality, either $p\in D^{\prime }$ or $p^{\prime }\in D$ – see Figure 4(ii) for an illustration – contradicting that $p$ and $p^{\prime }$ are both points on $\partial F$. $\mathrm{⊲}$ Now consider a circular sector $z$, defined by some arc $\beta$. Let $x$ be the apex of $z$ (which coincides with the center of the disk $D$ contributing $\beta$). If the angle at apex $x$ is large enough then $z$ is fat, but if the angle is very small then this is not the case. We therefore proceed as follows: we move the apex $x$ towards the midpoint of $\beta$ until the angle at $x$ is slightly larger than $\pi /2$; see Figure 4(iii). It is easy to see that the modified region (which is no longer a circular sector) is fat and convex. Moreover, no two modified regions share an apex anymore. With a slight abuse of notation, from now on we use $Z_F$ to denote the set of modified regions created for a flower $F\in ℱ$.

Let $Z(ℱ):={\bigcup }_{F\in ℱ}{Z}_F$. Note that $|Z(ℱ)|⩽4\cdot |ℬ(ℱ)|=O(n)$ and that $\mathrm{ply}(Z(ℱ))⩽2\cdot \mathrm{ply}(ℱ)=O(\log n)$; the latter is true since the regions created for a single flower $R$ are pairwise disjoint except at shared endpoints of boundary arcs. For each arc $\beta \in ℬ(ℱ)$, there is a region $z\in Z(ℱ)$ such that $\beta \subset \partial z$. Hence, the number of intersections between the arcs in $ℬ(ℱ)$ is upper bounded by the number of intersections between the regions in $Z(ℱ)$.

The proof is standard, but we sketch it for completeness. We charge the intersection between two regions $z,z^{\prime }$ to the smaller of the two regions, and claim that each region is charged $O(\mathrm{ply}(Z(ℱ)))$ times. To see this, consider a region $z\in Z(ℱ)$ and let $b$ be the smallest enclosing disk of $Z$. Let $b^{\prime }$ be the disk with the same center as $b$ such that $\mathrm{radius}(b^{\prime })=2\cdot \mathrm{radius}(b)$. Due to the fatness of the regions in $Z(ℱ)$, any region $z^{\prime }$ that intersects $z$ and is at least as large as $z$, will cover a constant fraction of the area of $b^{\prime }$. Hence, there can be at most $O(\mathrm{ply}(Z(ℱ)))$ such regions $z^{\prime }$. $\mathrm{⊲}$ This finishes the proof. $◀$ Observe that two flowers $F,F^{\prime }$ intersect iff the following holds: a boundary arc of $F$ intersects a boundary arc of $F^{\prime }$, or $F\subset F^{\prime }$, or $F^{\prime }\subset F$. Thus we can find all intersecting pairs of flowers – and, hence, all edges of the clique-based contraction $\mathscr{H}$ – as follows. (The algorithm below may report a pair of intersecting flowers multiple times, but this is not a problem.)

First, we construct the arrangement $𝒜(ℱ)$ induced by the flower set $ℱ$. Next, for each vertex of $𝒜(ℱ)$ that is the intersection of the boundaries of some pair of flowers $F,F$, we report that pair. Finally, we need to find the pairs of flowers $F,F^{\prime }$ such that $F\subset F^{\prime }$. To this end, we traverse the dual graph of $𝒜(ℱ)$, maintaining a list $ℒ$ of flowers containing the face we are currently in. Whenever we enter a flower $F$ for the first time, we report the pairs $(F,F\mathrm{’})$ for the faces $F\mathrm{’}$ that are currently in the list $ℒ$.

We obtain the following lemma.

Computing the collection $𝒞$ of cliques takes $O(n\log n)$ time by Lemma 3. It remains to analyze the time needed to compute the edge set $E_{\mathscr{H}}$ of the clique-based contraction.

For each clique $C\in 𝒞$, we can compute the corresponding flower $F(C)$ in $O(|C|\log |C|)$ time using a simple divide-and-conquer algorithm. Since each disk is part of only clique, this implies that the flower set $ℱ$ can be computed in $O(n\log n)$ time. Moreover, the total number of boundary arcs of the flowers is $O(n)$ because the complexity of a single flower is linear. Hence, we can construct the arrangement $𝒜(ℱ)$ in $O(n\log n+k)$ expected⁵⁵5We cannot use the deterministic algorithm for line-segment intersection by Chazelle and Edelsbrunner [10] because it does not work for curves. The deterministic algorithm for line-segment intersection by Balaban [3] also works for curves, but that algorithm does not seem to give enough information to construct the arrangement. time, where $k$ is the number of intersections between the boundary arcs, using a randomized incremental algorithm by Mulmuley [23]. Since $k=O(n\log n)$ by Lemmas 3 and 3, constructing the arrangement thus takes $O(n\log n)$ expected time. The traversal of the dual graph, including the maintenance of $ℒ$ takes $O(n\log n)$ time. Since the size of the list $ℒ$ is $O(\log n)$ at any time – this is because the ply of the flower set is $O(\log n)$ – we report at most $O(n\log n)$ pairs in total during the traversal. Thus, the total time to compute $E_{\mathscr{H}}$ is $O(n\log n)$. $◀$

Lemma 3 gives us the first ingredient we need to apply Theorem 1. The second ingredient is an algorithm that solves Bichromatic Intersection Testing for disks. As observed in previous papers [9, 21] this can be done in $O((n_B+n_R)\log n_R)$ time, as follows. First, compute the additively weighted Voronoi diagram $\mathrm{Vor}(R)$ on the centers of the set $R$ of red disks, where the weight of a center is equal to the radius of its corresponding disk. Next, query with the center of each blue disk $D$ in $\mathrm{Vor}(R)$ to find the red disk $D^{\prime }$ closest to $D$. Now $D$ intersects $\bigcup R$, the union of the red disks, iff $D$ intersects $D^{\prime }$. Since $\mathrm{Vor}(R)$ can be computed in $O(n_R\log n_R)$ time [17], after which it can be preprocessed for logarithmic-time point location in $O(n_R\log n_R)$ time [13], we can solve Bichromatic Intersection Testing in $O((n_B+n_R)\log n_R)$ time. We thus obtain our main result.

In the full version [11] we present a (slightly more complicated) deterministic algorithm to compute the edges of the clique-based contraction for ${𝒢}^{\times }[𝒟]$ in $O(n\log n)$ time. Using that algorithm instead of Lemma 3, we obtain an algorithm to compute shortest-path trees on disks graphs deterministically in $O(n\log n)$ time.

Our approach to construct a clique-based contraction for fat triangles is similar to the algorithm for disks. We now go over the various ingredients and explain how to adapt them, if necessary.

We first observe that Lemma 3.2 from Chan’s paper [5] actually holds for any type of objects. Hence, our Lemma 3 also holds for any type of objects. To construct the skip quadtree, the set $P(\mathrm{\Gamma })$ of disk centers is replaced by a set $P(\mathrm{\Gamma })$ that contains an arbitrary point in each object. Constructing the cliques can therefore be done in exactly the same way as before. Indeed, the crucial property was as follows: any set of disks intersecting the boundary of a region $R_{\nu }$ and whose size is at least $\frac{1}{6}\cdot \mathrm{size}(R_{\nu })$, can be stabbed by $O(1)$ points. This property also holds for fat objects.

Now let $C$ be a stabbed clique of fat triangles. We refer to the union of the triangles in $C$ as a spiky flower, and we denote it by $F(C)$. As before, we let $𝒞(\mathrm{\Gamma })$ denote the set of cliques created by our algorithm, and we define $ℱ(\mathrm{\Gamma }):=\{F(C):C\in 𝒞(\mathrm{\Gamma })\}$ to be the corresponding set of spiky flowers. Then Lemma 3 also holds for fat triangles – we can follow the proof verbatim, only replacing occurrences of “disk” by “fat triangle.”

It remains to prove the equivalent of Lemma 3 for fat triangles. To keep the terminology similar to the case of disks, we will refer to the edges of a spiky flower $F$ as boundary segments, and we denote the set of boundary segments of a flower $F$ by $ℬ(F)$. Furthermore, we let $ℱ:={\bigcup }_{\mathrm{\Gamma }\in \mathrm{\Xi }}ℱ(\mathrm{\Gamma })$ denote the set of spiky flowers created by our algorithm, and we define $ℬ(ℱ):={\bigcup }_{F\in ℱ}ℬ(F)$.

We apply the same proof technique as in the proof of Lemma 3: we cover the boundary segments of each spiky flower $F$ by a set $Z_F$ of non-overlapping fat “sectors” contained in the flower, as explained below, from which the lemma follows.

The number of boundary segments of a spiky flower is $O(n_F)$, where $n_F$ is the number of triangles defining $F$ [1, Section 3.2]. We create the set $Z_F$ for a spiky flower $F$ as follows. For each boundary segment $\beta$ of $F$, we create an isosceles triangle $z\subset F$ whose angles at the endpoints of $\beta$ are $\alpha /3$, where $\alpha$ is the fatness constant of the triangles; see Figure 5.

With a slight abuse of terminology, we refer to these isosceles triangles as sectors.

Each sector $z$ has one edge that corresponds to a boundary segment of $F$; we call this the external edge of $z$. The two other edges, which make an angle $\alpha /3$ with the external edge, are called internal edges.

Now assume for a contradiction that two sectors $z,z^{\prime }$ overlap. Since the external edge of any sector cannot properly intersect an (external or internal) edge of any other sector, there must be a crossing between an internal edge of $z$ and an internal edge of $z^{\prime }$. Let $x$ be this crossing, and let $e$ and $e^{\prime }$ be the external edges of $z$ and $z^{\prime }$, respectively; see Figure 5(ii). Assume without loss of generality that the distance from $x$ to $e$ is at least the distance from $x$ to $e^{\prime }$. Let $p$ be the point on $e^{\prime }$ nearest to $x$, and let $D$ be the disk centered at $x$ and touching $e$. Then $p$ is contained in $D$. Moreover, $D$ is contained in the triangle $\mathrm{\Delta }\in 𝒟$ contributing $e$ to the boundary of the spiky flower $F$. Indeed, if we were to expand the sector $z$ by making the angles at the endpoints of $e$ equal to $2\alpha /3$ then $D\subset z$, and this expanded sector is contained in $\mathrm{\Delta }$. Thus, $p\in \mathrm{\Delta }$, which contradicts that $p$ lies on an external edge. $\mathrm{⊲}$ As in the proof of Lemma 3, it now follows that the number of intersections between the sectors in $Z(ℱ)$ is $O(|Z(ℱ)|\cdot \mathrm{ply}(Z(ℱ)))$, which proves the lemma. $◀$ As before, we have the following corollary. Its proof is the same as the proof of Lemma 3; the only difference is that we can now use the algorithm by Chazelle and Edelsbrunner [10] to construct the arrangement defined by the flowers, thus avoiding the use of randomization.

The final ingredient that we need is an efficient algorithm for Bichromatic Intersection Testing for a set $B$ of $n_B$ blue triangles and a set $R$ of $n_R$ red triangles, where all triangles in $B\cup R$ are fat. Such an algorithm can be developed using standard machinery, as described next.

Let $A:=\{i\cdot (\alpha /2):0⩽i⩽\lfloor 4\pi /\alpha \rfloor \}$ be a set of $O(1/\alpha )=O(1)$ canonical directions, where $\alpha$ is the fatness constant of the triangles. Define a canonical segment to be a segment whose direction is canonical, and define a canonical chord of a fat triangle $\mathrm{\Delta }$ to be a canonical segment that connects a vertex of $\mathrm{\Delta }$ to its opposite side; see Figure 6(i).

Note that each vertex of $\mathrm{\Delta }$ admits a canonical chord. Let $S(\mathrm{\Delta })$ be a set of three canonical chords of $\mathrm{\Delta }$, one per vertex of $\mathrm{\Delta }$, and let $P(\mathrm{\Delta })$ be the endpoints of these chords (including the vertices of $\mathrm{\Delta }$).

Suppose that condition (ii) does not hold. Then there is a canonical chord $s\in S(\mathrm{\Delta })$ that intersects two edges of ${\mathrm{\Delta }}^{\prime }$, or all canonical chords in $S(\mathrm{\Delta })$ are disjoint from ${\mathrm{\Delta }}^{\prime }$. In the former case, $s$ separates a vertex $v$ of ${\mathrm{\Delta }}^{\prime }$ from its opposite side, which implies that $s$ intersects the canonical chord of $v$; see Figure 6(ii). Thus, condition (iii) holds in this case. In the latter case, ${\mathrm{\Delta }}^{\prime }$ must have a vertex inside $\mathrm{\Delta }$ and condition (i) holds; see Figure 6(iii). $◀$ Observation 4 implies the following lemma.

The data structure consists of three separate data structures, each handling one of the conditions in Observation 4.

For condition (i) we need a data structure for range searching with fat triangles in a set $V$ of $3n$ points, namely the vertices of the triangles in $R$. As observed by Gray [18, page 14], such queries can be answered in $O({\log }^{3}n)$ time with a structure of size $O(n{\log }^{2}n)$ that can be built in $O(n{\log }^{3}n)$ time.

For condition (ii) we use a union tree on the triangles in $R$. This is a binary tree $𝒯$ whose leaves correspond to the triangles in $R$, and whose internal nodes store the union of the triangles in their subtree, preprocessed for point-location queries. Checking if a query point $q$ is contained in any triangle in $R$ can be done in $O(\log n)$ by performing a point location at the root of $𝒯$. If this is the case, then we can find a witness triangle in $O({\log }^{2}n)$ time by walking down $𝒯$, always proceeding to a child whose union contains $q$. Since the union complexity of $n$ fat triangles is $O(n{\log }^{\ast }n)$ [2], the total amount of storage is $O(n{\log }^{\ast }n\log n)$. Note that the union at a node $\nu$ can be computed in $O(n_{\nu }{\log }^{\ast }{n}_{\nu }\log n_{\nu })$ time from the unions of its two children by a simple plane-sweep algorithm, where $n_{\nu }$ is the number of triangles in the subtree of $\nu$. Hence, the total preprocessing time is $O(n{\log }^{\ast }n{\log }^{2}n)$.

To handle condition (iii) we proceed as follows. Let $S_R:\{s\in S(\mathrm{\Delta }):\mathrm{\Delta }\in R\}$ be the set of canonical chords of the triangles in $R$. We will build $O(1/\alpha )$ different data structures on $S_R$, one for each of the $O(1/\alpha )$ possible directions of the query chord. To construct a data structure for a fixed direction of the query chord, we partition $S_R$ into $O(1/\alpha )$ classes, one for each canonical direction in $A$, and we build a separate substructure for each class $A_i$. Assume wlog that the query chord is vertical and that the chords in $A_i$ are horizontal. Then we can use an interval tree [12, Section 10.1] to answer queries in $O(\log n)$, using $O(n)$ space and $O(n\log n)$ preprocessing. (Using a point-location structure on the vertical decomposition of the chords in $A_i$ is another option.) Thus the total amount of storage is $O(n/\alpha )=O(n)$, the total preprocessing is $O((n/\alpha )\log n)=O(n\log n)$, and the total query time is $O((1/\alpha )\log n)=O(\log n)$.

Since all data structure work within the claimed bounds, the lemma follows. $◀$ We can now solve Bichromatic Intersection Testing for fat triangles in $O((n_B+n_R){\log }^3(n_B+n_R))$ time, by querying with each triangle $\mathrm{\Delta }\in B$ in the data structure provided by Lemma 4. This leads to the following theorem.

In the full version [11] we provide a better data structure for the range-query problem considered in Lemma 4: its construction time is $O(n{\log }^{2}n)$ and each query is then answered in $O({\log }^{2}n)$ time. Using this data structure, we obtain an $O(n{\log }^{2}n)$ algorithm to compute shortest-path trees on the intersection graph of fat triangles.