Efficient uses of the past
David Dobkin, J. Ian Munro · 1980
A failing of existing data structures for maintaining balanced trees is their inability to remember the situation they held at previous times. We propose a structure from which it is possible to efficiently reconstruct the state of the data it represented at any time. Applications of this data structure to a number of important problems in geometric computation are also given.