Nextag Interview Question
Developer Program EngineersCountry: India
Interview Type: In-Person
en.wikipedia.org/wiki/K-d_tree#Points_only_in_leaves
As said in above link, if the points are distributed randomly all across the space, we can do better than linear time with hacking around using method in the link.
PS: This may even qualify as a point-in-a-polygon variant and I'm not sure of its complexity. I'm off to flight now but will let you know if we can use this techinique as well.
It's not exactly true, because before you start to answer queries, you should build k-d tree, and it takes O(N log(N)) time, and after that each query will take O(logN) time.
This algorithm will be useful when there is one set of points and a lot of queries and the resulting complexity will be O(Q logN) where Q is number of queries, N is number of points.
If points given in random order, you can't solve this problem faster than O(N), because you should look at each point at least once, so you have to go through all the points and check distance between it and A
- V.Krestyannikov January 05, 2012