We get a figure like this, where the sweep line goes from left to right and the coloured regions indicate the best preceding anchor for each position. Most of the work is in maintaining the shapes of these regions, which we do with predecessor structures on the horizontal and diagonal boundaries.

2 likes 0 replies