Блог пользователя dreamplay

Points within radius R.
Автор dreamplay, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится -15 Проголосовать: не нравится

Yeah, bad idea

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Use k-d tree

→ Ответить