Here is the problem Given a set of N points and some query points, What is the farthest point from the set to each of the query points. Here are a couple of questions: Is it the same time complexity when finding the nearest neighbor? Where can I find some theory about this?
If there is a better way (with the same or less time complexity) to solve this problem using a suitable amount of code please let me know...
How about computing the convex hull for this as the farthest point will always lie on the convex hull.
Complexity O(nlogn + qh) = O(nlogn) (using graham scan) where h = no. of points on the convex hull ,and q = no. of queries
Edit: Worst Case complexity for the above is o(nq). But on the average it should be much faster.
Convex Hull will only work for small polygons with many points inside, and for two dimensional space, for bigger dimensional space it is a real pain. What I am looking for is an O(q logn + n logn) or O(q sqrt(n) + n sqrt(n)) worst case complexity algorithm
Will be there any difference when the distance is euclidean or manhattan?
If we consider 2D points + Manhattan distance then Fenwick tree can be used to do offline queries.
Sorry, I forgot to add this to the blog, some points might be deleted on the course of the queries..
Could you explain your offline version of Fenwick Tree for this problem when distance is Manhattan?
For each point i, let it be the origin then we can divide other points into 4 quadrants. For the 3rd quadrant where x[k] <= x[i] and y[k] <= y[i], the Manhattan distance between i and j is equal to
x[i] - x[k] + y[i] - y[k] = (x[i] + y[i]) - (x[k] + y[k]).Based on this observation, we first sort all points by x ascending, then by y ascending. Iterate in the sorted order and use a Fenwick tree to store min(x[k] + y[k]) for all k <= i and y[k] <= Y (don't forget to map the y values into [1..n]). For the other 3 quadrants, just perform a rotation and do the same.
One similar problem with minimum distance requirement: http://www.spoj.com/problems/GANNHAT/