I_love_tigersugar's blog

Closest Point Pair
By I_love_tigersugar, 11 years ago, In English

Given N distinct points on the plane. Find the pair of point with the smallest (and largest) Euclid distance between them.

I only know the Brute-Force O(n^2) algorithm to solve this.

Can someone give me any faster algorithm?

Thanks in advance.

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

»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

There is a divide-and-conquer solution in O(n*log(n)), but this one is easier to implement,

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

the smallest (and largest)

I thought these are two completely different problems and you should not mix them. I believe the shortest distance could be found efficiently, but it is not so for the greatest one.

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

    Convex hull + two pointers on it are O(NlogN) solution to farthest points problem.

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

      I agree. I failed to note we are speaking of 2D space, sorry. But I was bewildered by the yellow color of the author's handle (since planar case is discussed in wikipedia). :)

      I thought that closest pair algorithm could be generalized for any number of dimensions with the same asymptotic, but not the furthest pair. Though I may be wrong — am I?

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

    Largest distance... well, it's between points on a convex hull. Out of points inside triangle , the one most distant from point must be or .

    Also, the distance of vertices of a convex polygon from an arbitrary vertex of this polygon would (as we travel along the perimeter) first keep increasing and then keep decreasing, so we can bin-search for the first pair of vertices , of which the first is farther than the second.

    By repeating this for all possible choices of vertex , we can find the most distant pair in .

    Edit: ninja'd :D

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

      No need to bin-search. You can find the largest distance between two points on convex hull with rotating calipers method in O(k), where k is count of points in CH. There is good article here, but on russian. You can google-translate it or try to understand the main idea from pictures.

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

        To everyone their own. I know the rotating calipers method (from CTU Open 2013, one problem was about finding a minimum perimeter bounding rectangle for a set of points), but I'd rather bin-search, because I could code it quickly and painlessly. And you still need to construct the convex hull in time.

        BTW you link is neither clickable nor readable. Maybe it's because of some special characters — anyway, it's better to not use the link as the shown text.

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

          Of course bin-search is easier to implement, and == , but if we know that points are on CH, we can compute it in linear time

          Yes, I know. idk why old link didn't work, but now shortened link works fine

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

      Are you sure that the distances from a fixed vertex of a convex polygon first increases and then decreases? Say that the polygon is very similar to an ellipsis, and the ellipsis is very thin. Take vertex roughly in the middle, then the distance first increases, then decreases, then increases, and then decreases again.

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

        Not so sure now :D

        I remember that some nice property should hold there, though.

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

        I think for points that are part of a maximum distance pair it holds.

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

          Why? You can have a situation similar to this:

          the maximum distance is between the bottom central point and one of the red points. But the red parts can be arbitrarily complicated: you can be within the circle, then outside, then within again, and so on...

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

            "you can be within the circle, then outside, then within again, and so on" But then the polygon wouldn't be convex would it? That said, I can't prove that what I said is true, but the rotating calipers method makes a very similar assumption it seems (or maybe I'm wrong).

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

              Why wouldn't it be convex? I can repeat the red part multiple times (after scaling down a little bit) and the resulting polygon will still be convex :)

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

                I see. Clever, I guess this settles the argument :)

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

You can sort the point first by x-coordinate, then by y-coordinate. Call your current shortest distance D. When go through point P[i], get a set S consist of all point to the left of P[i] which Manhattan distance to P[i] smaller or equal than D. Run brute-force in S. One can prove that S has O(1) size. Good luck.

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

Smallest distance can be calculated in O(n*log(n)) for any dimension.

Largest distance also known as Diameter of a Set of Points.

→ Reply