Closest pair of points in a Plane 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:


Find the minimum x co-ordinate(minX) and minimum y(minY) co-ordinate.
Name the point origin= (minX,minY)
Find the distance of all points from this origin and store it in a vector dist[].
Sort the vector dist[].
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.
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?
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.