0

Suppose we have two sets of points, say A and B (both of size O(n)) in the plane. Can we find farthest pair of points each being in A & B in O(n) time?

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
user2311963
  • 143
  • 6
  • Do you want to find farthest pair of points each being in A & B? I suggest you rephrase your question and add what you have you done so far. – Rishit Sanmukhani Apr 22 '16 at 07:17
  • @Rishit, Thank you. I changed it. – user2311963 Apr 22 '16 at 07:20
  • 1
    I don't think you could do it in O(n) time. But it is possible in O(nlogn) time. – Rishit Sanmukhani Apr 22 '16 at 07:22
  • 1
    yes..we can do in O(nlogn) time by finding convex hull or farthest point Voronoi diagram for the point set A. I would like to know whether better performance is possible or not. – user2311963 Apr 22 '16 at 07:25
  • By an information theoretical argument: simply producing the indexes of all farthest neighbors takes n bits per point, for a total of n Log n bits. –  Apr 24 '16 at 21:29

1 Answers1

1

No, you can not calculate the furthest point for each point in O(n). The best you can obtain is O(n log n) with a 2-d tree. You can do this with a technique, similar to finding a closest point.

Read a more detailed answer here where I show a couple of other approaches to solve a similar problem.

Community
  • 1
  • 1
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
  • 1
    You got the green tick even though you seem to be answering the *closest* pair problem, not the *farthest* pair problem...? – j_random_hacker Apr 22 '16 at 14:30
  • @j_random_hacker essentially the same coz u can reverse the comparator –  Apr 22 '16 at 15:05
  • 1
    @willywonka_dailyblah: Maybe that works for the 2-d tree solution, I don't know, but it definitely doesn't work for e.g. the "grid" solution in the linked answer. In general, if you know that a is close to b, and that c is close to a, then you know that c is at least somewhat close to b -- but if you replace "close to" with "far from", the inference fails. – j_random_hacker Apr 22 '16 at 15:29
  • @j_random_hacker the idea is the same for both problems. The question has not asked how to solve the problem, but rather asked whether it is possible to solve it in O(n). So my answer is `no`, and here is some explanation to a related problem. You can modify a grid solution - now you will need in the beginning to find the furthest grids, and check points in the furthest grids. – Salvador Dali Apr 22 '16 at 18:42
  • As you don't mention in the answer itself that it addresses only a related question, I'm going to -1. Will undo if you mention there that closest point is just a related problem, and that some solutions to it can be adapted to the farthest point problem. You also don't give any reason *why* there cannot be any solution better than O(n log n) (to either problem). – j_random_hacker Apr 23 '16 at 13:43
  • @j_random_hacker I modified it. One thing to mention is that is it really hard to prove that something can not be done with some complexity. For example there is not proof that matrix multiplication can't be done in O(n^2), or dijkstra can be done faster. In majority of such cases we just say that it can't be done now, because the best we know now is this complexity. – Salvador Dali Apr 23 '16 at 21:00
  • @SalvadorDali: That's (unfortunately) true in general, but in the case of the closest point problem, there is a reduction to the element uniqueness problem, which is one of the rare problems that has a known lower bound (in this case, O(n log n)). I've removed my -1. – j_random_hacker Apr 24 '16 at 11:01
  • My -1 because there is no justification of the impossibility. Also, referring to a "similar" problem is often misleading. Think of Eulerian and Hamiltonian paths. Also, the approaches cited in the link have no guarantee of O(n Log(n)) efficiency. –  Apr 24 '16 at 21:35