[anonymoushn]

You can divide the work into twice as many independent chunks of the same size like so:

If you were going to divide the image into K horizontal strips of triangles, instead divide the top half into K/2 horizontal strips of triangles and divide the bottom half into K/2 horizontal strips of triangles. To make things easier at the end, please include a 1px tall overlap between the top and bottom parts. Work downward from the top and upward from the bottom until you reach the middle. At the middle, for each column, you have the cost of the top half of the minimum seam that includes that pixel and the cost of the bottom half of the minimum seam that includes that pixel. So you can add those together then take the min as before.