### 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.