AnotherRound's blog

Algorithm for farthest point query
By AnotherRound, history, 8 years ago, In English

I recently thought of the following problem: Given a set of N points in the plane(static), we have Q queries. In each query we are given a point with its coordinates and we have to output the point in the set which has maximal distance to the queried point. What is the most efficient algorithm for solving the task(which is not too long/complex to be used in competitions)? Also, what if we could add/remove points from the set? I couldn't think of anything else that bruteforcing every possible point in our set, but I'm looking for something faster(maybe O(logN) per query?).

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

»
8 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Please correct me if I made a mistake. I assume that there is no query like insert or remove point from plane.

It's obvious that farthest node must belong to convex hull of those set of points (even if queried point is in inside or outside). So we are storing convex hull points.

Let's say that query point is (x, y). Make center of coordinate system in that point. We have to deal with every quadrant separately. I think that is not a problem to zone points that belong to some quadrant, by simply binary searching them by x and y. For simplicity fix one quadrant, let's say that we fix first. I claim (here is a maybe flaw) that distances from our (x, y) to points in first quadrant increase than decrease, by going in counter clockwise direction, because of convexity of convex hull. These points will form 4 adjacent intervals, which finally means that ternary search is applicable. By doing 4 ternary searches we can find most distant point in for every quadrant and finding quadrants for every point can be done by 4 binary searches in if we store points of convex hull in (counter)clockwise order in structure like vector. That would give us complexity of per query.

I'll explain my idea of storing points. Divide convex hull in upper and lower part, which Andrew's monotone chain convex hull algorithm actually does. Store them in vector. We will maybe have to deal with some corner cases if x separator line cross part of upper and lower part of convex hull. I think that binary searching on points stored like I described would be possible.

I think that any idea that stick to convex hull can not support dynamic version of this problem since dynamic convex hull can be found in Ω (n).

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

    The only problem is that you cannot do a ternary search on such a function.

    → Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Wild guess, without proof:

Offline version: compute convex hull, find center point C of convex hull (average x, average y), sort queries by angle (0, 0) - C, find the furthest point to first query in O(n), move pointer in clockwise direction as you answer queries.

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

For the static version take a look at the farthest point Voronoi diagram, it gives you a logarithmic solution. With a standard binary addition trick you can add points at the expense of increasing the complexity by additional log factor. I doubt that the fully online problem with deletions can be properly solved, though.

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

    Could you please provide me an implementation of Voronoi diagram for studying purposes?

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

      Answering to all of you who requested me an implementation: no, I won't give it to you. Me myself not only haven't ever implemented the furthest point Voronoi diagram, but I don't even have an idea how exactly it is built. So, please, use Google. You have all the needed keywords.

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

    Which algorithm would you propose for generating Voronoi diagram?

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

    The most important thing that it should run in O(N*log2(N)) time, of course, another implementations aren't so useful in ACM area.

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

    Can you provide a link or do a quick explanation for this version of Voronoi diagram, please.

    → Reply