2
$\begingroup$

I want to write an algorithm to find the closest pair of points among n points in an XY-plane. I have the following approach in my mind:

  1. Find the minimum x co-ordinate(minX) and minimum y(minY) co-ordinate.
  2. Name the point origin= (minX,minY)
  3. Find the distance of all points from this origin and store it in a vector dist[].
  4. Sort the vector dist[].
  5. Traverse through the vector dist and for each i=1 to n-1, do dist[i+1]-dist[i] and keep track of the minimum of these and the pair that form this minimum.
  6. Return minimum and the pair.

I am not sure if this algorithm would work because of how triangle inequality works.

Any help on why this algorithm should/should not work?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ > do dist[i+1]-dist[i]. What does this mean? What are you "do"-ing at this point? $\endgroup$
    – jmite
    Apr 16, 2016 at 22:29
  • $\begingroup$ So dist is my vector that stores the distance of each point from "our" origin(minX,minY). So dist[i] means, the distance of ith closest point from the origin. $\endgroup$
    – a_123
    Apr 16, 2016 at 22:31
  • $\begingroup$ I am subtracting dist[i] from dist[i+1]. $\endgroup$
    – a_123
    Apr 16, 2016 at 22:32
  • $\begingroup$ Okay, you have a value, which is dist[i+1]-dist[i]. What are you doing with that value once you've computed it? $\endgroup$
    – jmite
    Apr 16, 2016 at 22:34
  • $\begingroup$ So as I keep computing dist[i+1]-dist[i] for each i, I keep track of the minimum value found so far. At the end, I declare the minimum value as the closest distance among distances between all pairs. $\endgroup$
    – a_123
    Apr 16, 2016 at 22:38

3 Answers 3

Reset to default
5
$\begingroup$

No, your approach will not work

Let $O$ be your chosen origin. Let $A$, $B$ be two of your other points. $OAB$ form a triangle.

The vector you have in mind would contain the distances $\overline{OA}$ and $\overline{OB}$. You can not determine the distance $\overline{AB}$ using only the two other sides of the triangle. You would need at least one of the angles for that.

As for a concrete counter example:

$O = (0,0), A = (0,2), B = (0,5), C = (2,0)$

so your vector would be:

$\overline{OA} = 2, \overline{OC} = 2, \overline{OB} = 5$

The differences are:

$\overline{OA}-\overline{OC} = 0$

$\overline{OC}-\overline{OB} = -3$

$(C, B)$ forms the minimum of but the closest pair is $(A, B)$ with a distance of 3.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! I liked the explanation. So can we find the angle by the slope of the line and then use that angle in our algorithm? I remember tan(theta)= (x2-x1)/(y2-y1). So we can get the angle also with the distances and then can we use the angle to find the closest pair? $\endgroup$
    – a_123
    Apr 16, 2016 at 22:59
  • $\begingroup$ This is not always a right-angled triangle. It might not be a triangle at all (the points could form a line). To get the angle you'll have to use trigonometric laws. Im not sure how that angle will help you though, except for using it to calculate the missing distance. But you could get that distance directly since you already have the coordinates of the points. $\endgroup$
    – user4758246
    Apr 16, 2016 at 23:28
  • $\begingroup$ After sorting the vector dist, can we be sure that the actual closest pair will always be consecutive in the vector? $\endgroup$
    – a_123
    Apr 16, 2016 at 23:43
  • $\begingroup$ No, try for example A(0,1), B(2,0), C(0,3) $\endgroup$
    – user4758246
    Apr 17, 2016 at 9:07
0
$\begingroup$

I think your algorithm doesn't produce the correct results, because, as you mentioned, two points might have a close distance from your computed origin, but that doesn't mean that there are no two points that are closer.

I'm not sure, but I think there is no correct algorithm faster than $O(n^2-n)$, which is what you get when comparing them all with each other.

You can use an approximation, though. You could divide the space in sections and then compare only the vertices that fall into the same section. The problem is now to find the best division of the space.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for answring Marcel! There is a divide and conquer strategy that gives correct results in O(nlogn) time. I do not want to use the divide and conquer approach, although O(nlogn) is the complexity I am striving for. $\endgroup$
    – a_123
    Apr 16, 2016 at 23:01
  • $\begingroup$ This was a big deal back in the day, for efficient game programming. Look at some of the old Graphics Gems series of books for code that does this. E.g. make a determination that a point is not a closer distance before doing expensive instructions. $\endgroup$
    – JDługosz
    Apr 17, 2016 at 1:22
0
$\begingroup$

Just a minor improvement to comparing each point with each other point: Sort the points in x order. Then you take the first point. You compare it with other points sorted in x order. However, if you found the closest pair of points so far at a distance d, you can stop that search as soon as the distance in the x direction alone is larger than d. To make the search more efficient, check the square of the distance (which is dx^2 + dy^2) instead of the actual distance, avoiding calculation of a square root.

This should be nowhere near O (n log n), but substantially better than O (n^2).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.