1
$\begingroup$

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:

  1. For each pair $0\le i\le N-1$ in the list find its subtraction with $\forall{j}$ except $i\neq{j}$.
  2. Sort the list of resultant subtractions.
  3. Selection of each pair in the list corresponds to the subtraction in increasing order & 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)
$\endgroup$
  • 1
    $\begingroup$ I am not sure if I understand you approach correctly, but you mean first compute all distances between each pair of points, then sort that distances, and finally how do you select the optimal path according to your points and their order? Sorting may not give you an optimal path with respect to the given points. $\endgroup$ – fade2black Jul 30 '17 at 10:47
  • $\begingroup$ I do not understand the precise question. It seems the order of the route is fixed and there are no obstacles. Does that mean the main problem is to compute the number of steps to go from consecutive points $(x_1,y_1)$ to $(x_2,y_2)$? $\endgroup$ – Hendrik Jan Jul 30 '17 at 12:50
  • $\begingroup$ Oh @HendrikJan I think you are correct. I am editing the problem now. $\endgroup$ – Mr. Sigma. Jul 30 '17 at 12:57
  • 1
    $\begingroup$ But there is a formula for that distance. Compute $|x_2-x_1|$ and $|y_2-y_1|$ and then some addition and $\max$ and or $\min$.That would leave linear complexity? $\endgroup$ – Hendrik Jan Jul 30 '17 at 13:14
  • 2
    $\begingroup$ I see, I interpreted it as "sequence" and posted $O(K)$ solution. $\endgroup$ – fade2black Jul 30 '17 at 17:56
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I think minimum spanning tree won't give result. It's like we have to calculate shortest Euler path, not a tree. $\endgroup$ – Mr. Sigma. Jul 30 '17 at 9:39
  • $\begingroup$ Eular path is a path which visits every edge once, but here we need to visit every node(i.e. every vertex (x,y) and not every edge $\endgroup$ – Prateek Mirdha Jul 30 '17 at 18:12
0
$\begingroup$

UPDATE: after additional clarification it turned out that OP meant "set of points" instead of "sequence of points", and so the problem is reduced to TSP. Ignore the following solution which assumes "sequence of points".

The first approach is that you could solve using Floyd-Warshall algorithm in $O(|V|^3)$ time.
1) Convert the grid into a weighted graph where $w(v_i,v_j) = 1$ for each neighbouring pair of points $(p_i,p_j)$ on the grid. I assume that every move in any of the eight directions from a point takes 1 step (but you may use a different metric).
2) Compute shortest paths for each pairs of vertices (points on the grid) $(v_i,v_j)$, by storing them in the matrix $M$, where $M[i][j]$ means the shortest path from point $p_i$ to the point $p_j$, using Floyd-Warshall algorithm.
3) Then for the given sequence of points $[p_1(x_1,y_1),\dots, p_k(x_k, y_k)]$, compute the sum $M[p_1][p_2] + M[p_2][p_3] + \dots + M[p_{n-1}][p_n]$ (The shortest path from $p_1$ to $p_2$ plus the shortest to $p_3$ plus $\dots$).

You could take a different approach (a greedy algorithm). Given a sequence of points $[p_1(x_1,y_1),\dots, p_k(x_k, y_k)]$, you first compute the shortest path from $p_1$ to $p_2$ (using Fredman-Tarjan algorithm, using Fibonacci heaps) in $O(E + V\log{V})$ time, then from $p_2$ to $p_3$, and so until the last point. So, its complexity is $O(K(E + V\log{V}))$, where $K$ is the number of points $p_i$. To improve further observe that each vertex has at most eight neighbours and so the graph has at most $8V/2 = 4V$ edges, and hence the time complexity is $O(K(4V + V\log{V}))$ which is $O(KV\log{V}))$.

Yet another approach to improve the greedy algorithm is using BFS for finding the shortest path from one point to another one since your graph has edges only of weight 1 (may be considered as unweighted). BFS works in $O(V+E)$ time or $O(V)$ since your vertices have constant number of neighbours (eight at most). So the running time may be reduced to $O(KV)$.

And finally, you may compute the shortest path from one point $p_i$ to another $p_j$ in $O(1)$ by $\max(|x_i-x_j|, |y_i-y_j|)$ given coordinates $(x_i, y_i)$ and $(x_j,y_j)$ and reduce the algorithm to $O(K)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.