jlcastrillon's blog

KD Tree Help
By jlcastrillon, 12 years ago, In English

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

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will be there any difference when the distance is euclidean or manhattan?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    If we consider 2D points + Manhattan distance then Fenwick tree can be used to do offline queries.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sorry, I forgot to add this to the blog, some points might be deleted on the course of the queries..

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you explain your offline version of Fenwick Tree for this problem when distance is Manhattan?

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 5   Vote: I like it +6 Vote: I do not like it

          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/

          → Reply