Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid? Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions :

(x, y) to 
(x+1, y), 
(x-1, y), 
(x,   y+1), 
(x,   y-1), 
(x-1, y-1), 
(x+1, y+1), 
(x-1, y+1), 
(x+1, y-1) 


You are given a sequence of points. Give the minimum number of steps in which you can cover all of them. You start from the first point.
Example:

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2


My approach: 


For each pair $0\le i\le N-1$ in the list find its subtraction with  $\forall{j}$ except $i\neq{j}$.
Sort the list of resultant subtractions. 
Selection of each pair in the list corresponds to the subtraction in increasing order &amp; keep counting $\max(x_{2}-x_{1},y_{2}-y_{1})$ till the end.


Now,


If it is correct it's complexity is $\Theta(n^{2}\log n)$ because of subtraction between $\frac{n(n-1)}{2}$ pairs + sorting in $n^{2}\log n$. Is there any better efficient algorithm? (Updated from Prateek's answer)
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.