Algorithm for arranging Cartesian points

Question

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?

Klapp

Do you always start from 0,0 (or the bottom-left-most point)? Or can you start from any point? – Grounder

i like the question, but you would have to specify specifics, for instance do you go horizontal first (try to find a point with x value +1 but same y value as the current point) or vertical? what happens if two points are the same? can you go backwards? ie from (2,2) to (2,1)? – Stilbite

Wait, are you looking for a path from a specific start/end-point, or a path that goes through every point? I interpreted it as the former, but everyone else seems to think it's the latter... in that case, can you go through the same point more than once? – Reflector

Cartesian products are popular lately. Seen this: blogs.msdn.com/b/ericlippert/archive/2010/06/28/… or this: stackoverflow.com/questions/3093622 My brain is much to squished today to read either of the above, maybe as a hail mary they can help you out. – Acquisition

Are you looking for a total ordering? or just an ordering? – Nipha

@cape1232, I can start from any point, not necessariy (0,0) – Klapp

@Jesse Naugher, horizontal or vertical doesn't matter. It's guranteed that no two points will be same. I can go backwards. – Klapp

@BlueRaja I am looking for a path that goes from every point. I can go through a point more than once. – Klapp

@Nipha - I am not very sure. – Klapp

Answer 1

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.

Hochman

Answer 2

You can construct a graph with the vertices being your points, and the edges being the valid steps.

What you're then looking for is a Hamiltonian path for this graph. This, in its general form, is an NP-complete problem, which means there is no known efficient solution (i.e. one that scales well with the number of points). Wikipedia describes a randomized algorithm that is "fast on most graphs" and might be of use:

Start from a random vertex, and continue if there is a neighbor not visited. If there are no more unvisited neighbors, and the path formed isn't Hamiltonian, pick a neighbor uniformly at random, and rotate using that neighbor as a pivot. (That is, add an edge to that neighbor, and remove one of the existing edges from that neighbor so as not to form a loop.) Then, continue the algorithm at the new end of the path.

A more efficient solution might exist for this particular situation, though.

Glucinum

-1: You have only shown that Hamiltonian Path is harder than solving this problem. You haven't shown that the current problem is NP-Complete. – Hochman

I went through that algorithm, not very clear to me.. Can you explain a bit more, may be with psuedo code? – Klapp

Hmm, you're right, that description is pretty unprecise. Maybe this helps: #1987683 – Glucinum

Answer 3

Think of it as a graph where each node as at most four edges. Then do depth/breadth-first search.

Reflector

This is most likely to be the correct answer because the question says nothing about optimality or the like. – Donets

Answer 4

This could be simplified as minimizing the distance between each consecutive point. Going from (0,0) to (0,1) is simply 1 unit, but going from (0,0) to (1,1) is actually sqrt(2). So if you arrange the points into a graph, and then perform a simple minimum-total-distance traversal (traveling salesman), it should arrange them correctly.

Edit: If you never want a step that would be larger than 1, simply do not add any edges that are greater than 1. The traversal will still work correctly, and ignore any paths that require a movement > 1.

Edit 2: To clarify further, you can use any edge selection algorithm you wish. If you're ok with it moving 2 spaces, as long as the space is not diagonal, then you may choose to put an edge between (0,2) and (0,4). The minimum distance algorithm will still work. Simply place the edges in a smart way, and you can use any number of selection criteria to determine the outcome.

Hatchway

someone deleted a comment that was quite good; the ordering (0,0) -> (1,1) -> (5,0) is valid in your criteria but not his. – Nipha

@Nipha I updated my answer to show what I was thinking in terms of that particular situation. It's quite easy to avoid that situation by controlling which edges are actually drawn, and keeping the basic traversal algorithm intact. – Hatchway

no. I don't think anyone is suggesting you step larger then one. The issue is not stepping in diagonals. those three points I mention, although, do not have an ordering specified under the authors criteria. but a list like this would be better suited to the discussion, (3,2) -> (0,2) -> (0,3) -> (1,3). Here, although the step (3,2) -> (1,3) would be minimal, it should be avoided. – Nipha

That is assuming a solution is possible, and that you can go through points more than once. What do you do with { (0,0), (1,0), (0,1) }? More information is needed. – Donets

My edit stands. It depends on the intent, but you can draw edges any way you wish. It's pretty easy to compare two points and decide whether or not to draw an edge. For example, (3,2) and (0,2) share the y, so it can have an edge. However, (3,2) and (0,3) should not have an edge in this case, because neither x nor y is shared. I was assuming he wanted consecutive points only ("changes x or y by 1"), but you can use any selection requirement you wish. – Hatchway

@drharris: with { (1,0), (1,1), (0,1), (2,1) } your traveling salesman has a legitimate path but would have to go through (1,1) at least twice. How would your algorithm respond to this set? – Donets

@NickLarsen it depends on your rules for that, specifically the traversal algorithm you use. He may be ok with multiple visits to a node, or not. There are different algorithms (but known ones) for both cases. If the algorithm cannot find a valid path starting with any of the nodes, it can be assumed there is no valid path for the condition the algorithm is programmed to handle. – Hatchway

@drharris: I'm just thinking it is better to state your assumptions along side your solution, instead of leaving those up to the reader to decipher. – Donets

Answer 5

One way to do this is to create two sorted lists of the coordinates. One sorted by x and one sorted by y. Then, recursively find a solution.

Code coming (not sure what language yet; maybe pseudocode?)... Edit - nevermind, since my answer isn't as good as some of the others anyways.

Leopardi

Answer 6

How about a brute force recursive REXX routine... Try all possible paths and print those that work out.

/* rexx */
point. = 0  /* Boolean for each existing point */
say 'Enter origin x and y coordinate:'
pull xo yo
point.xo.yo = 1  /* Point exists... */
say 'Enter destination x and y coordinate:'
pull xd yd
point.xd.yd = 1  /*  Point exists... */
say 'Enter remaining x and y coordinates, one pair per line:'
do forever
  pull x y
  if x = '' then leave
  point.x.y = 1
end

path = ''
call findpath xo yo path
say 'All possible paths have been displayed'
return

findpath: procedure expose point. xd yd
arg x y path
if \point.x.y then return               /* no such point */
newpoint = '(' || x y || ')'
if pos(newpoint, path) > 0 then return  /* abandon on cycle */
if x = xd & y = yd then                 /* found a path */
  say path newpoint
else do                                 /* keep searching */
  call findpath x+1 y path newpoint
  call findpath x-1 y path newpoint
  call findpath x y+1 path newpoint
  call findpath x y-1 path newpoint
  end
return 

Example session:

Path.rex
Enter origin x and y coordinate:
0 0
Enter destination x and y coordinate:
2 2
Enter remaining x and y coordinates, one pair per line:
0 1
1 1
2 1
1 2

 (0 0) (0 1) (1 1) (2 1) (2 2)
 (0 0) (0 1) (1 1) (1 2) (2 2)
All possible paths have been displayed

Don't try this on anything big though - could take a very long time! But then the question never mentioned anything about being an optimal solution.

Tobytobye