Given n points (x,y) on a euclidean plane. A radius R.
Input: Q queries of form (a,b)
Output: For each query, points within radius R
Suggest a solution to this?
Expected complexity: Better than brute force, asymptotically.
Given n points (x,y) on a euclidean plane. A radius R.
Input: Q queries of form (a,b)
Output: For each query, points within radius R
Suggest a solution to this?
Expected complexity: Better than brute force, asymptotically.
Auto comment: topic has been updated by dreamplay (previous revision, new revision, compare).
Yeah, bad idea
For example, with very big R all our points will be located in the square (a — r, b — r, a + r, b + r) and it still brute force.
Use k-d tree