dreamplay's blog

Points within radius R.
By dreamplay, history, 10 years ago, In English

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.

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
10 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by dreamplay (previous revision, new revision, compare).

→ Reply
»
10 years ago, hide # |
← Rev. 3  
Vote: I like it -15 Vote: I do not like it

Yeah, bad idea

→ Reply
  • »
    »
    10 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
10 years ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

Use k-d tree

→ Reply