own shortcut.

#### Extending the tree

Algorithm \[alg:extend\] summarizes the steps required to extend the tree $T$ with a new node. Node $G[i,j]$ has three *candidate parents*, $G[i-1, j]$, $G[i-1, j-1]$, and $ G[i, j-1]$. Each pair of these candidates has an NCA. For the actual parent of $G[i,j]$, we select the candidate $c$ such that for any other candidate $c'$, the maximum value from $c$ to their NCA is at most the maximum value from $c'$ to their NCA—both excluding the NCA itself. We must be consistent when breaking ties between candidate parents. To this end, we use the preference order of $G[i-1, j] \succ G[i-1, j-1] \succ G[i, j-1]$. Since paths in the tree cannot cross, this order is consistent between two paths at different stages of the algorithm. Note that a preference order that prefers $G[i-1,j-1]$ over both other candidates or vice versa results in an incorrect algorithm.

$G$ is a grid of non-negative values; any path in tree $T$ is locally correct node $G[i,j]$ is added to $T$ and any path in $T$ is locally correct

$parent(G[i, j]) \leftarrow$ candidate parent with lowest maximum value to NCA

Remove the dead path ending at $G[i-1, j-1]$ and 