Circle-Segment Intersection Queries in Connected Geometric Graphs

Peyman Afshani, Yannick Bosch, Sabine StorandtIsaac 2025 · DOI

TL;DR

This paper introduces a novel data structure for efficiently finding intersections between query circles and line segments that form connected geometric graphs. By leveraging the graph's connectivity, they achieve significantly faster query times and reduced construction complexity compared to general segment sets, making it practical for large-scale applications like road networks.

What Problem Does This Paper Address?

The core problem is efficiently finding intersections between a query circle and a set of line segments. This is a fundamental task in computational geometry with applications ranging from robotics to map matching. While existing methods exist for general sets of segments, they often suffer from high preprocessing times or query costs, especially for variable-radius circles. The authors identify a crucial gap: these methods don't exploit the inherent structure present when segments form a connected geometric graph, such as road networks. This lack of structural awareness leads to suboptimal performance on such datasets.

Methods

The paper's main contribution is a new data structure that exploits the connectivity of the input graph. The key ideas are:

  • Balanced Connected Graph Partitioning: They develop an algorithm to recursively partition the edges of a connected graph into two smaller, connected subgraphs. This is achieved by operating on the graph's abstract structure, not its geometry, ensuring connectivity is maintained. This partitioning creates an "edge partition tree" of logarithmic depth.
  • Circle-Graph Intersection Oracles: For each node in the edge partition tree (representing a connected subgraph), they build a specialized "oracle." This oracle efficiently answers whether a query circle intersects any segment within that subgraph. This oracle leverages geometric transformations and a combination of convex hull intersection tests and Segment Voronoi Diagrams (SVDs) for efficient decision-making.
  • Recursive Querying: Queries are answered by traversing the edge partition tree. At each node, the oracle is consulted. If it indicates no intersection, the search along that branch is pruned. If an intersection is possible, the query recurses on the children. This drastically reduces the search space.
  • Type-(i) and Type-(ii) Intersections: The paper explicitly handles two types of intersections: where one endpoint is inside the circle and the other outside (type-i), and where both endpoints are outside but the segment itself crosses the circle (type-ii). The oracles are designed to detect both.

Datasets

The authors evaluated their approach on real-world road networks:

  • A part of Germany (approx. 1.1 million edges).
  • The road network of Taiwan (approx. 5 million edges).

These are not newly introduced benchmarks but are standard datasets for evaluating graph-based algorithms.

Key Insights and Ideas

  • Connectivity is Key: The most significant insight is that the connectivity of the geometric graph is a powerful structural property that can be exploited to dramatically improve circle-segment intersection query performance. General methods overlook this.
  • Recursive Partitioning for Efficiency: Breaking down the problem into smaller, connected subproblems via the edge partition tree allows for localized and efficient oracle computations.
  • Specialized Oracles Outperform General Solutions: By tailoring intersection detection to subgraphs within the tree, they avoid the overhead of general-purpose data structures, leading to faster queries.
  • Practical Performance Matters: The paper emphasizes that while theoretical bounds are important, their approach also demonstrates strong practical performance on large, real-world datasets, outperforming standard AABB tree implementations.

Key Results

  • Theoretical Bounds:
    • Construction time and space: $O((n + C) \log^3 n)$, where $n$ is the number of edges and $C$ is the number of edge crossings.
  • Query time: $O(k \log^3 n)$, where $k$ is the number of intersecting segments. This is a significant improvement over general methods that might have $O(n^{2/3 + \epsilon})$ query times.
  • Practical Performance:
    • On a graph with 1.1 million edges, their data structure (CSIDS) achieved query times in the 20-40 ms range, significantly faster (up to 8x) than refined AABB queries and orders of magnitude faster than naive AABB queries.
  • For a graph with 5 million edges, construction time was reduced from over an hour to about 9 minutes by using top/bottom cutting techniques. Query times remained in the 20-40 ms range.

Limitations and Future Work

  • Oracle Computation: The current approach computes the circle-graph intersection oracle independently for each node. Future work suggests optimizing this by using bottom-up merging strategies or randomized incremental algorithms to derive parent oracles from child solutions, potentially reducing construction time.
  • Fractional Cascading: The authors propose exploring fractional cascading to potentially improve query times, especially when dealing with nested convex hulls during tree traversal.
  • Lower Bounds: Investigating theoretical lower bounds for data size and query time trade-offs in the connected graph setting is suggested to understand the limits of improvement.
  • Broader Applications: Extending the approach to other graph types like triangle meshes is mentioned as an interesting future direction.
  • Engineering Improvements: Further engineering ideas could enhance scalability for even larger datasets.

Summary updated

BibTeX
@inproceedings{afshani2025circle,
  author = {Peyman Afshani and Yannick Bosch and Sabine Storandt},
  title = {{Circle-Segment Intersection Queries in Connected Geometric Graphs}},
  booktitle = {Isaac},
  year = {2025},
  doi = {10.4230/lipics.isaac.2025.3},
}
Figure