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.

Comments

  1. Thanks. There was a problem I was struggling with, being a non-CS student.
    http://www.spoj.pl/problems/RUNAWAY/

    ReplyDelete

Post a Comment