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?
dist[i+1]-dist[i]
. What are you doing with that value once you've computed it? $\endgroup$