[Solved]: Closest pair of points in a Plane

Problem Detail: 

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?

Asked By : a_123

Answered By : user3158988

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56046

 Ask a Question

 Download Related Notes/Documents