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.
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.
If the distance is Eucledian, you should use Voronoi diagram.
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 :)