Most efficient way to check graph edge or node overlap with circle border on euclidean plane (2D space)

Question

Suppose that there is a given graph, in terms of nodes with specific placement on the euclidean plane (2d space) (for ex. node A is at (7,14) 7 is x-axis and 14 is y-axis) and edges that specify which nodes are connected with which (weights or directed or not, are irrelevant).

Now suppose that we are given a circle (by specifying the center and the radius). What is the most efficient way in terms of complexity to find, if any, all parts of the graph (nodes or edges) that overlap with the circle border?

Is there a specific data structure that the graph must be saved as to enable quick indexing ?? A kind of binary search for 2d points for example (if a similar thing even exists) ???

Keep in mind that the reason i am pinpointing algorithmic efficiency is the fact that the input data sets are huge. Millions or maybe billions of nodes and edges. Subsequently if the approach is parallelizable too, it would really be of great help.

Update: I've found that 2 approaches may be feasible, r-trees and spatial hashing. I do not know though if r-tress support(and perform well on) equality queries (for the circle border), and if it is possible to incorporated the edges in a spatial hashing implementation.

Answer 1

As you suggest, I would use a spatial index structure, such as quadtree, r-tree, or kd-tree.

If the edges are (usually) comparatively short, you could simply store their bounding boxes (axis aligned rectangles that have the edge as diagonal).

If you are only for overlap/intersection with the circle border, I would chop the border into a series of small edges (a few dozen or hundred?). For each resulting edge, you create a rectangle (again, axis aligned bounding box) and use the rectangle as a query window to find all stored rectangles that intersect/overlap with the query rectangle.

Since overlapping rectangles do not necessarily indicate overlapping diagonals, you will have to do some extra checks to see whether the resulting rectangles really belong to intersecting edges.