moakhey's blog

Farthest two points from each other
By moakhey, 9 years ago, In English

Hi, I was thinking about this problem: given a set of points in a plane, find the two points which are the farthest from each other. Logically, these two points should lay on the convex hull, so I came up with a solution with NlogN complexity: for each point A0 on the convex hull, do a binary search to find the farthest point from A0. (We have the set of points on the convex hull ordered such that they form a cycle). We take the point in the middle of index i, if d(A0,Ai)>d(A0,A(i+1)) then we should only consider the points A1..Ai, otherwise we only consider points Ai..An, and we repeat recursively until we get only one point. I think i have a simple proof by contradiction, but I want your opinion about its correctness/efficiency.

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

»
9 years ago, # |
← Rev. 3   Vote: I like it -13 Vote: I do not like it

I believe that is indeed the correct algorithm, and I highly doubt a linear one exists. A cool optimization that will however not change the asymptotic complexity is to find the point on the convex hull using two pointers. You can try to figure it out yourself but it is possible to get linear solution by rotating two pointers in the right way. In such case the complexity will be dominated by the sorting used for finding the convex hull, which is still

however O(NlogN) :)

Edit: Oh well, turns out it ain't correct, quite silly of me :P

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    and I highly doubt a linear one exists

    Lower bound of NlogN was proved a long time ago. You need NlogN to check separability of two sets of numbers. Assume that you have two sets of numbers a[i] and b[i]; map every number from first set into point on circle where it intersects with line y=a[i]*x in first quadrant, and map every number from second set into point on circle where it intersects with line y=b[i]*x in third quadrant. Now to check that received set of points have a diamterer equal to diameter of a circle you need to check if there exist such pair i,j that a[i]==b[j]. But it can't be done faster than NlogN.

    → Reply
»
9 years ago, # |
  Vote: I like it -19 Vote: I do not like it

I think binary search here is wrong and you should use ternary search, also you can easily proof that ternary search is correct :)

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

    Can you please provide your proof of ternary search correctness?

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

      It is obvious that d(A0,Ai) is not monotonic, but i think the sequence increases until it reaches the farthest point and then start decreasing ,otherwise the hull won't be convex right?

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

        No, it's not right, look at my comment below

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -15 Vote: I do not like it
      • there's no proof but consider this, for each point x on the convex hull, we need to find the point with the farthest distance from this point and check it with our global maximum, as you said that point is somewhere on convex hull, so we gotta check points on convex hull, buff I say you form a function called F(P) which is the distance of point P from point x, now if you put all the points of convex hull except x in the function, you'll receive a function with ternary search property, and also because of the convex property there is exactly one peak. :)
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 3   Vote: I like it +10 Vote: I do not like it

        Take a regular polygon with 1000000 sides. Take a point P[0] at the middle of its diameter. Now take sequence of points P[1],...,P[2000000], where P[2*i] is i-th vertex of this polygon and P[2*i-1] is middle of i-th side of this polygon.

        Take new polygon formed by points P[0],...,P[1000000]. All those points will lie on convex hull of given polygon. However, if we denote D[i]=Distance(P[0],P[i]) then we have D[1]<D[2]>D[3]<D[4]>D[5]<D[6]>D[7]<...

        This shows that your function does not have ternary search property at all.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it -20 Vote: I do not like it

          It's seems that you misunderstood the convex hull, I suggest you visit http://en.wikipedia.org/wiki/Convex_hull :)

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

            I should be prepared to be smashed by Lebron :)

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

              Please don't tell my teammates that I don't understand what does convex hull means, they'll probably start looking for new teammate then :)

              I am lazy to draw some pictures by myself, so I'll take a random one from Internet as an example.

              Look at this hexagon.

              How does convex hull of OCBGAF looks? It is OCBGAF itself. If you will add point I as middle of CB and point J as middle of AF, you'll get OCIBGAJF. And convex hull of this polygon will be OCIBGAJF — once again, every vertex here belongs to a hull (you may move points I,G,J a bit closer to a circle and point O a bit upward to make it strictly convex).

              OC=OB=OA=OF=R. OI=OG=OJ<R. Therefore OC>OI<OB>OG<OA>OJ<OF.

              Now you may take regular polygon with larger number of sides instead of hexagon, and build same example. It don't even have to be a regular polygon — take center of a circle, some random sequence of points on upper semicircle S1 and some random sequence of points S2 where S2[i] lies on segment connecting S1[i] and S1[i+1].

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

                I was just kidding after I realized how stupid I was so I made a joke, sincerely hoping that you're not upset :)

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

    After providing a proof of ternary search correctness, please, take a look at my example.

    Consider A0 is a point of right isosceles triangle near right angle, A1 and A3 — are points near other angles, and A2 is a middle of hypotenuse. Easy to see, that d(A0, A0) < d(A0, A1) > d(A0, A2) < d(A0, A3) > d(A0, A0)

    So, d(A0, *) function is not unimodular and ternary search is not applicable

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

Your algorithm is not correct because d(A0, Ai) is not a monotonic sequence so we can't use binary search here.
However, you're absolutely right about using the convex hull.
In fact, finding a pair of points with the largest distance a well known problem and its solution requires Convex Hull + Two Pointers method.

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

It is funny that when that question comes to consideration there is ALWAYS someone who claims that sth here is monotonic and binary search would work or two pointers with pushing one forward as long as distance increases (two pointers techniques works but with different approach and that is subtle how to do it and why it works). Look at this thread: http://codeforces.com/blog/entry/11179#comment-162768 :)

→ Reply