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.