nodes with a growth node as parent. These nodes are incident to at most one face. All shortcuts of these nodes are indicated.[]{data-label="fig:sinksandshortcuts"}](discreteSinksAndShortcuts)

#### Shortcuts

To avoid repeatedly walking along the tree to compute maxima, we maintain up to two *shortcuts* from every node in the tree. The segment between the node and its parent is incident to up to two faces of the tree. The node maintains shortcuts to the sink of these faces, associating the maximum value encountered on the path between the node and the sink (excluding the value of the sink). Fig. \[fig:sinksandshortcuts\] (b) illustrates some shortcuts. With these shortcuts, it is possible to determine the maximum up to the NCA of two (potentially diagonally) neighboring growth nodes in constant time.

Note that a node $g$ of the tree that has a growth node as parent is incident to at most one face (see Fig. \[fig:sinksandshortcuts\] (c)). We need the “other” shortcut only when the parent of $g$ has a living parent. Therefore, the value of this shortcut can be obtained in constant time by using the shortcut of the parent. When the parent of $g$ is no longer a growth node, then $g$ obtains its 