Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?
Actually I did not get exactly what you are trying to do in Step 1 but complexity of this algorithm should be $O(n^{2} log(n))$ because you will get $(n*(n-1)/2)-c$ elements i.e $O(n^{2})$ elements and then to sort them you will get $O(n' log(n'))$ complexity where $n'=O(n^{2})$.

Their is a full proof solution for this problem and it also has complexity of $O(n^2 log(n))$.

Step 1. Lets assume all co-ordinates are nodes from 1,2.....N.First find 
 distance b/w all the vertices in O(n^2).
Step 3. Find minimum spanning tree which can be formed using Prim's 
 algorithm or Kruskal's algorithm whose complexity is O(E log(E)) 
 where 'E' is the number of edges and in our case E=n^2.


Hope that helps.