Блог пользователя moakhey

Farthest two points from each other
Автор moakhey, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится -13 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    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.

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you please provide your proof of ternary search correctness?

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -11 Проголосовать: не нравится

      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?

      → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится
      • 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. :)
      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

        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.

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
            Проголосовать: нравится -20 Проголосовать: не нравится

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

          → Ответить
          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            I should be prepared to be smashed by Lebron :)

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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

              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                  Проголосовать: нравится -8 Проголосовать: не нравится

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

                → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

    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

    → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.net/blog/entry/11179#comment-162768 :)

→ Ответить