Biased Finger Trees and Three-Dimensional Layers of Maxima

We present a method for maintaining biased search trees so as to support fast finger updates (i.e., updates in which one is given a pointer to the part of the tree being changed). We illustrate the power of such biased finger trees by showing how they can be used to derive an optimal O(n log n) algorithm for the 3-dimensional layers-of-maxima problem and also obtain an improved method for dynamic point location