### Nearest Point problem

This was the question asked to Anirudh in his google interview. He could not do it (who cares! He got the job :D)

I could give a vague but correct answer :)

You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.

Of course, O(n) can be done {Compare best-so-far value for each point}

But since our set of n points is constant, we would want some pre-processing so that the query time is reduced.

:) Interesting problem. Interesting solution.

I could give a vague but correct answer :)

You have n points on a 2-D plane. You have to execute the query, given a fresh point, which of these n points is closest to it. This is termed as gas-station problem or postman problem, as in asking the question which is the closest gas-station/post-office from some place.

Of course, O(n) can be done {Compare best-so-far value for each point}

But since our set of n points is constant, we would want some pre-processing so that the query time is reduced.

:) Interesting problem. Interesting solution.

The solution can be found on this wikipedia link:

ReplyDeletehttp://en.wikipedia.org/wiki/Nearest_neighbor_search

Thanks. There was a problem I was struggling with, being a non-CS student.

ReplyDeletehttp://www.spoj.pl/problems/RUNAWAY/