So the problem is following: given N points in a database (edit: just assume for the moment it's 2 arrays x[] and y[]), each with coordinate (x[i], y[i]), and queries with format (X,Y,R), list all points in the circle with center (X,Y), radius R.
Edit - Input constraint: x=[-180,180], y=[-180,180]
Which Python library can solve this the fastest way possible? I'm looking for O(log(N) + K) time complexity per query, and <= O(n * log(N)^2) space requirement, where K is the output length.
Solution 0: Loop over N points, use Pythagoras to check.
-> Memory: O(N). Time per query: O(N)
Solution 0.1:
Same as above, but add small things like sorting by x, and use binary search to start searching only points with coordinate x[i] >= X - R. Use squared distance instead of distance, etc
-> Time per query: still O(N) but faster
Solution 1 Quadtree. Assume points are centered around (0,0). Root node of tree is at (0,0), containing 2D spaces (x=[-inf,inf],y=[-inf,inf]). Each node has 4 child: where each child contains 1/4 quadrants of the father. So whenever we go down a level, search space is reduced by 75%. Keep going down deeper until the current node is outside the query circle, or contains no data point.
-> Memory: maybe O(n * log(N)^2)? , time: ~~O(log(N)^2)
Is their any python library that already solve this problem?