Circle-Segment Intersection Queries
in Connected Geometric Graphs

There are interesting special cases of the circle-segment or disk-segment intersection problem, which have been studied in the literature:

• $\mathrm{■}$

  If all input segments have length zero, the input is simply a set of points. Thus, the problem degenerates into reporting all points on the boundary of a query circle or inside a query disk. The latter is also known as the disk range searching problem. Disk range searching in ${ℝ}^2$ can be transformed into halfspace range searching in ${ℝ}^3$, for which a data structure of size $𝒪(n\log n)$ allows to answer queries in $𝒪(\log n+k)$ [5].

• $\mathrm{■}$

  If the circle has a radius of zero, it degenerates into a point. Then, the circle/disk query asks for the segments that contain the query point, also known as segment stabbing problem. If the segments are assumed to be disjoint, queries can be answered in $𝒪(\log n)$ after a $𝒪(n\log n)$ preprocessing phase that produces a data structure of linear size [12].

For the general case, the data structures for type-(i) and type-(ii) circle/disk-segment intersection described in [16] are the state-of-the-art. For variable radius, first a partition tree on the segment endpoints is constructed [19] after projecting the points to ${ℝ}^3$. Here, the point set is recursively partitioned using simplices, such that in the resulting hierarchical tree, the number of points in each child partition is a constant fraction of the number of points in the parent partition and only a bounded number of children intersect a query object at each level. To only retrieve the intersecting segments with an endpoint inside the circle, the data structure is augmented such that halfplane composition queries can be answered. Also type-(ii) intersections can be identified with the help of halfplane query compositions. This gives rise to a data structure of size $𝒪(n)$ with query times in $𝒪(n^{2/3+\epsilon }+k)$ for $\epsilon >0$, as well as the other trade-offs mentioned in the introduction.

For fixed radius, type-(i) and type-(ii) intersections are computed with two different data structures. For type-(i), first a stabbing path is computed on the segment endpoints. This path is guaranteed to intersect a given query circle at most $𝒪(\sqrt{n})$ times. On this path, a tree data structure is constructed, which is augmented with a halfplane query data structure at each node. Using geometric transformations and dualization, this allows to identify the segments with an endpoint outside and an endpoint inside the query circle. For type-(ii) intersections, a reduction to triangle stabbing is described and proper data structures for this use case are leveraged. In [8], the data structure for circle-segment queries with fixed radius $r$ from [16] was refined and improved for the case in which the input segments form a path to show improved theoretical running times for map matching. However, for practical implementation, an AABB tree is used in [8], as the nested data structures described in [16] are rather intricate and expensive to construct. The AABB tree, available as a ready-to-use implementation in CGAL, is a hierarchical data structure in which each node corresponds to an axis-aligned bounding box (AABB) that encapsulates the set of geometric primitives associated with its descendant leaf nodes (in this case, the input segments). While often fast in practice, it cannot guarantee output-sensitive query times as the bounding box of a segment set might intersect a given geometric query object $𝒬$ (as a circle) while none of the contained segments actually have an intersection with $𝒬$.

In [4], the segment-circle intersection problem was studied, in which the roles of the input and the query are switched compared to our setting. Here, the input is a set of $n$ circles and the query object is a segment. It was shown that the circles can be preprocessed into a data structure of size $𝒪(n{\log }^{2}n)$ such that queries can be answered in $𝒪(n^{2/3}{\log }^{2}n+k)$ where $k$ denotes the output size. For disks, the query time reduces to $𝒪(\sqrt{n}{\log }^{2}n+k)$.

There are also other contexts in which the connectivity structure of the input segments plays a crucial role. For example, in [3], the input is a set of segments and the goal is to report the connected components that intersect a given query segment. In [6], it was shown that intersections between two sets of line segments can be computed much faster if each of the two sets is connected.

We propose a new data structure for circle-segment or disk-segment intersection queries on connected planar graphs with $n$ edges, which can be constructed using $𝒪(n{\log }^{3}n)$ time and space, and answers queries with output size $k$ in time $𝒪(k{\log }^{3}n)$. This is a significant improvement over the general case, where a data structure of (near-)linear size yields query times in $𝒪(n^{2/3+\epsilon }+k)$ for $\epsilon >0$. Thus, especially for queries with small output size, our query time is vastly superior. If the input graph is non-planar and there are $C$ crossings among the segments, the construction time and the space consumption increase to $𝒪((n+C){\log }^{3}n)$ but the query time stays the same. At the heart of our data structure lies a scheme which partitions the edges of the connected input graph, such that the resulting partitions have balanced size and each still form connected components. We show that such a partitioning can be computed in time $𝒪(n)$. Applying this result recursively allows us to efficiently construct an edge partition tree¹¹1We remark that despite the similar name our data structure differs substantially from the partition tree concept for point sets described in [19]. of logarithmic depth. We then equip each such edge partition with an oracle that decides whether for a given query circle $𝒬$ there is some edge in the set that intersects $𝒬$. Based on this oracle, the tree can be traversed efficiently on query time.

We also carefully describe how to implement the proposed data structure and demonstrate its usefulness in a proof-of-concept evaluation on different road networks. While road networks are non-planar, the number of crossings $C$ between the edges is typically in $\mathrm{\Theta }(\sqrt{n})$ [15] and thus we expect our data structure to perform well. This is confirmed in the experiments where we observe fast construction times even on large networks, and improved query times over the AABB tree implementation provided by CGAL.

In the construction of our intersection search data structure, we follow the well-established paradigm of recursively dividing our problem into smaller subproblems until they reach a tractable size. To accomplish this while also being able to utilize the connectivity of the input graph, we require an algorithm that partitions the edge set of the input graph such that the connectivity property is maintained in each partition. Existing geometric partitioning methods (for example, median- or grid-based) are oblivious to the connectivity structure and thus are not guaranteed to produce the desired result. The method we propose does the opposite as it completely ignores all geometric information and instead operates only on the abstract graph. It is thus also applicable to non-geometric graphs. Edge partitioning has previously been studied in the context of distributed graph algorithms and parallelization [9, 22]. However, there the goal is to minimize communication cost introduced by the partitioning or to minimize node duplication (which turns out to be NP-hard). However, our focus is on balanced partitioning into connected components. In the remainder of this subsection, we prove the following central theorem.

We now describe the partitioning algorithm in detail and then prove its correctness to establish the theorem. The algorithm starts by constructing a spanning tree of $G$ via a DFS run from an arbitrarily selected source node $s$. Let $T_v$ denote the nodes of the subtree of the DFS-tree that is rooted at node $v$. The following observation sketches how we can use the notion of $T_v$ to achieve our goal of connected edge partitioning.

But we still need to take care of the size bound for each partition. Thus, we would like to efficiently compute the function $\varphi (v):=|E(T_v)|$ that assigns to each node the number of edges incident to the nodes in $T_v$. Initially, we set $\varphi (v)=0$ for all nodes $v$. We then consider the nodes one after the other using a post-order traversal of the DFS-tree and update the $\varphi$-values of the current node $v$ as well as its parent node $par(v)$ in the DFS-tree. We will maintain the invariant that at the moment that $v$ is processed, all $\varphi$-values are less than $\frac{1}{3}n$. This condition is clearly fulfilled after the initialization phase.

Let us now consider the algorithm steps for processing a node $v$. As we use post-order traversal of the DFS-tree, we know that $v$ is the last node to be processed in $T_v$. We first check whether , where $deg(v)$ denotes the degree of $v$ in $G[E]$. If that is the case, we add $deg(v)$ to $\varphi (v)$ and then proceed to add the new $\varphi (v)$ value to $\varphi (u)$ where $u=par(v)$. If we still have , we are done with $v$ and proceed to the next node in the post-traversal order. Clearly, our invariant is maintained in this case. Otherwise, if $\varphi (u)\ge \frac{1}{3}n$, we also know that $\varphi (u)\le \frac{2}{3}n$, as our invariant guaranteed that $\varphi (u)$ was smaller than $\frac{1}{3}n$ prior to processing $v$ and we only updated the parent of $v$ as held as well. Accordingly, with $v_1,\mathrm{\dots },v_s$ be the children of $u$ that were already processed up to this point (and thus contributed to $\varphi (u)$), we set $E_1:={\bigcup }_{i=1}^{s}E(T_{v_i})$ and $E_2=E\setminus E_1$. The resulting partitions are each connected, as $E_1$ contains all edges induced by $T_u$ and additionally only edges with at least one endpoint in $T_u$, while $E_2$ contains all induced edges of $\{T_s\setminus T_u\}\cup \{u\}$ and additionally only edges with at least one endpoint in this node set.

If, however, $\varphi (v)+deg(v)\ge \frac{1}{3}n$, we know that edges incident to nodes in $T_v$ already suffice to form $E_1$. If additionally $\varphi (v)+deg(v)\le \frac{2}{3}n$, we simply return $E_1=E(T_v)$ and $E_2=E\setminus E_1$. If the degree of $v$ is too large to include all of its incident edges in $E_1$, we only use $\frac{2}{3}n-\varphi (v)$ many, giving priority to edges $\{w,v\}$ with $par(w)=v$. Note that there are less than $\frac{1}{3}n$ such prioritized edges, as otherwise $\varphi (v)$ would have been equal to or larger than $\frac{1}{3}n$ already, which would contradict our invariant. Therefore, we are sure to include all edges induced by $T_v$ and therefore, again, guarantee connectivity of the resulting partitions.

Thus, the described algorithm reliably produces edge partitions $E_1$ and $E_2$, whose induced graphs are connected. However, we did not take double counting of the edges into consideration so far. An edge $e=\{a,b\}\in E$ with $a,b\in T_v$ might contribute twice to $\varphi (v)$, as both $deg(a)$ and $deg(b)$ are part of the sum. Therefore, the $\varphi$-values might overestimate the real number of edges in the respective subtree by a factor of up to 2. Thus, we can so far only guarantee a weaker size bound than the one promised in Theorem 1.

Given a connected graph $G[E]$, our goal is to construct an efficient decision oracle that returns true if a given query circle $𝒬$ has a type(i)- or a type(ii)- intersection with some edge in $G$ and false otherwise.

For our oracle, we utilize the well known geometric transformation in which points $p=(x,y)\in {ℝ}^2$ are mapped to points $p^{\prime }=(x,y,x^2+y^2)\in {ℝ}^3$ by a projection function $\psi (p)=p^{\prime }$, and a circle $𝒬$ with center $c=(a,b)\in {ℝ}^2$ and radius $r$ is mapped to the plane $z=a(2x-a)+b(2y-b)+r^2$ in ${ℝ}^3$ by a function $\rho (𝒬)=z$ such that $p$ is inside $𝒬$ iff $\psi (p)$ lies below $\rho (𝒬)$ and outside $𝒬$ iff $\psi (p)$ lies above $\rho (𝒬)$. These transformations are also applied in [16]. Let know $\mathrm{\Psi }(E):=\{\psi (p)|\{p,q\}\in E\}$ denote the set of segment endpoints in the graph after applying the transformation via $\psi$. Further let $CH(\mathrm{\Psi }(E))$ denote the convex hull of the resulting three-dimensional point set. We now show how these structures can be utilized to detect intersections of type-(i).

We are now ready to describe and analyze the full circle-segment data structure and the respective query answering algorithm.

Combining the insights from Theorem 1 and Theorem 7, we first construct an edge partition tree data structure, in which each node represents a connected subgraph of $G$, and then equip each such node with a decision oracle. To report all segment intersection with a query circle $𝒬$, we first apply the transformation to the three-dimensional plane $\rho (𝒬)$. Then, we use the following recursive algorithm for query answering, with the initial call being to root node of our data structure: For the current data structure node, which represents some connected edge subset $E^{\prime }$, we ask the associated oracle whether there is any segment in $E^{\prime }$ that intersects $𝒬$. If the answer is false, we stop. Otherwise, if the answer is true, we recursively call the algorithm on both children of the current node. We also stop if we reach a leaf node, which represents a single segment, and include this segment in the output set if it indeed intersects $𝒬$. Figure 4 illustrates the query answering process on a small example graph.

As baseline, we use the the AABB tree implementation provided by CGAL. It is a hierarchical data structure, in which each leaf node stores a geometric object and each internal node stores the bounding rectangle of all the objects in the respective subtree. It is constructed by dividing the input set of geometric objects roughly in half, computing the respective bounding rectangles, and then continuing recursively on both subsets until the leaf nodes are reached, which store the objects themselves. In our case, the leaves store the segments of the input graph $G(V,E)$. In a query, given a geometric object, we check whether its bounding rectangle intersects the bounding rectangle associated with the root node of the AABB tree. If this is the case, both children are checked as well. If not, the search is aborted at the respective node. If a leaf node is reached and the final check confirms an intersection, the geometric object stored in said leaf node is added to the output. While often fast in practice, the theoretical running time can be huge in the case that the bounding rectangle of the query object intersects many bounding rectangles associated with the tree nodes, but there are no actual intersections between the query object and the elements stored in the tree leaves. This happens particularly often if the query object is not an area (as a disk) but rather an area boundary (as a circle). Here, any segment fully contained in the circle will create a bounding rectangle that intersects the one of the circle, although the segment itself does not intersect the circle. To improve the performance of our baseline, we therefore do not query the segment AABB tree with the bounding rectangle of the circle, but instead cover the circle with eight rectangles of much smaller total area, see Figure 5. We refer to this method as the refined AABB query.

As benchmarks, we used two large real-world road networks, namely a part of Germany (Figure 6) with roughly 1.1 million edges and the road network of Taiwan (Figure 8) with about 5 million edges. The Germany graph has $C=2550$ edge crossings and the Taiwan graph $C=22920$.

Constructing our circle-segment intersection data structure took less than 12 minutes on the Germany graph. The construction time is dominated by the segment Voronoi diagram computations for all subgraphs contained in the edge partition tree. In Figure 7, we compare the query times of our data structure to those of the refined AABB queries. We observe that except for very small query circle radii, our data structure is clearly superior. Even for large output sizes, the query times stay below 30 milliseconds and are at the peak about a factor of 8 faster than the respective refined AABB queries and two orders of magnitude faster than the naive AABB queries. Thus, we only consider the refined AABB queries in the upcoming experiments. We think that the mild increase of the query time with the output size besides the shown theoretical running time of $𝒪(k{\log }^{3}n)$ can be explained by many paths from the root to a leaf that contain an intersecting segment share long common prefixes (while the theoretical worst-case analysis assumes them to be disjoint). Moreover, most of the occurring intersections are of type-(i). Our circle-graph oracle confirms such an intersection in time $𝒪(\log n)$ and then does not need to call the more expensive oracle for a type-(ii) intersection. Thus, in practice we have fewer and more efficient oracle calls than assumed in the theoretical analysis.

To deal with even larger graphs within a reasonable construction time, we observe that we can cut the top of our edge partition tree as well as the bottom levels. If we cut top levels, we then have to deal on query time with multiple root nodes, but we avoid the most expensive oracle construction steps on the large edge partitions close to the root. We remark that multiple root nodes can also be used in case the input graph is not connected but consists of (few) connected components. Cutting the bottom levels implies that we stop the recursive edge partitioning approach not only if we are down to single segments but already when the partition size drops below a certain threshold $t\in \mathbb{N}$. For the resulting leaf nodes, we do not construct the circle-graph intersection oracles but instead perform a simple intersection check for each contained segment with the query circle. As this limits the number of tree nodes, it helps to safe space. Furthermore, it is expected that the rather complex oracles we construct are only effective if the respective segment size is sufficiently large. We applied top and bottom cutting to the road network of Taiwan. This reduces the construction time significantly, from more than an hour to roughly 9 minutes. In Figure 9, we measure the impact of these data structure engineering techniques on the query time. Again, we observe that the refined AABB query times increase significantly with the query radius and the output size, reaching up to about half a second. Our query times, however, are again in the 20-40 millisecond range, although the search now starts from 76 root nodes (for most of which the oracle immediately returned a negative answer).

While it would of course also be interesting to conduct experiments on other types of graphs (for example, triangle meshes), our proof-of-concept study clearly shows the potential of our newly proposed data structure to accelerate the circle-segment queries on connected geometric graphs even for large edge sets.