I have few Cartesian points of the form : (x,y)
where x and y both are non-negative integers.
For e.g.
(0,0) , (1,1), (0,1)
I need an algorithm to arrange the above points
in such a way that going from one point to other
changes either x or y by 1.
In other words, I would like to avoid
diagonal movement.
So, the above mentioned points will be arranged like :
(0,0), (0,1), (1,1).
Similarly for (0,0),(1,1),(0,2)
there is no such arrangement possible.
I am not sure about what to call it
but I would call it Manhattan ordering.
Can anyone help?
If you are looking for an arrangement that does not repeat vertices:
What you seem to be looking for is a Hamiltonian Path in a Grid Graph.
This is known to be NP-Complete for general Grid Graphs, see Hamilton Paths in Grid Graphs.
So you can probably try your luck with any of the approximate/heuristic/etc algorithms known for Hamiltonian Path/Euclidean Traveling Salesman Problem.
If you are looking for an arrangement that can repeat, but want the minimum possible number of points in the arrangement:
This is again NP-Complete. The above problem can be reduced to it. This is because the minimum possible walk has n vertices if and only if the graph has a hamiltonian path.
If you are just looking for some arrangement of points,
Then all you need to do is check if the graph is connected. If it is not connected, there can be no such arrangement.
You can do a depth first search to figure that out. The depth first search will also give you such an arrangement in case the graph is connected.
If you want something closer to optimal (but in reasonably fast time), you can probably use approximation algorithms for the Euclidean Traveling Salesman problem.