0

As the pseudo code in the paper

4. If k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
5. x ← V[k + 1]
6. Else
7. x ← V[k − 1]+1
8. y ← x − k

the line 4 indicate that if k is not -D or D, than take the one which has a greater x, than find out the snake. This confused me, shouldn't I calculate both v[k-1] and v[k+1] and find out which path is further? What if I chose the one with bigger x as start point, while turns out that the our point will lead to a further path?

And what's more, according to this:

Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in diagonal k and then follow diagonal edges until it is no longer possible to do so or until the boundary of the edit graph is reached.

I think the author suggest that both (x’,y’+1) and (x"+1,y") (in this case, the v[k-1] and v[k+1]) should be calculate.

So any idea what I'm missing?

1 Answers1

0

I think the paper missed a proof, which is very simple, but I think the missing will lead to some confusion (for me), so I gives this proof here:

in page 6, line 4, the code is as below:

 f k = −D or k ≠ D and V[k − 1] < V[k + 1] Then
    x ← V[k + 1]
 Else
    x ← V[k − 1]+1

I don't think lemma2 will lead to this, the purpose of lemma2 is to proof this problem can be solved with a greedy strategy. And according to Given the endpoints of the furthest reaching (D − 1)-paths in diagonal k+1 and k−1, say (x’,y’) and (x",y") respectively, Lemma 2 gives a procedure for computing the endpoint of the furthest reaching D-path in diagonal k. Namely, take the further reaching of (x’,y’+1) and (x"+1,y") in diagonal k and then follow diagonal edges until it is no longer possible to do so or until the boundary of the edit graph is reached. The normal way is to get both points which extends from v[k - 1] and v[k + 1] and figure out which is a further reach path. But this will lead a double-culculate. Here's proof why only check V[k − 1] < V[k + 1] works:

lemma4: if v[k - 1] < v[k + 1], then path followed by v[k + 1] with a vertical edge with a snake will be the further rearched path in diagonal k.

proof: let's make v[k - 1] to x1 and v[k + 1] to x2. so the point followed by x1 in diagonal k is (x1 + 1, x1 + 1 - k)(go right), the point followed by x2 is (x2, x2 - k)(go down); the y position is useless here. then the problem changes to: if x1 < x2, then x1 + 1 <= x2 since x1 < x2 -> x2 - x1 > 0 assume that x1 + 1 > x2, then x2 - x1 < 1, so 0 < x2 - x1 < 1. But in edit graph, the basic move is 1, the 0 < x2 - x1 < 1 will never happen, so the assumption is wrong, so x1 + 1 <= x2.

I'v post this and a implementation on https://github.com/psionic12/Myers-Diff-in-c-/blob/master/README.md, you are welcome to discuss.