NeverSayNever's blog

Minimum Distance Query
By NeverSayNever, history, 9 years ago, In English

Hi frendz,

Recently one of my friend ask me following question which i am unable to solve efficiently. I am putting that question here.

PROBLEM : Given N points in 2 dimensional plane and Q queries each containing a point X in the 2 D plane. Find the minimum distance of this point X from the given N points.

NOTE If anyone has any solution considering either Eucledian distance or manhattan distance. Please post it here.

Any help will be highly appreciated.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If distance is manhattan:

We turn plane on 45 degrees. (x, y) -> (x + y, x — y).

Then we do binomial search and find sum in square.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the distance is Eucledian, you should use Voronoi diagram.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Or you can try to check magic number of points with nearest manhattan and Chebyshev distance. There is a big probability that this will work due to weak testset :)

    → Reply