TY - JOUR
T1 - Efficient uses of the past
AU - Dobkin, David P.
AU - Munro, J. Ian
N1 - Funding Information:
In this paper. we discuss data struc tures, for maintaining history. Data base applications often deal with insertions and deletions from a static universe of elements. We may wish to add to the insertions and deletions queries regarding the ordering of active elements in the data base at some previous time. Or. we may wish to determine statistics concerning e1ements affected by changes to the data base during a given interval of time. Surprisingly. the solutions of the problems mentioned above have direct applications to a number of important problems in geome try concerning repres en ta t ions of 3dimensional objects. We consider the basic problems: *This work was done while the second author was a Visiting Professor at the University of Arizona. Portions of this work were supported by the National Science Foundation under Grant MCS79-03428 and the National Science and Bngineering Research Council under Grant~A8237.
Funding Information:
This work was done while the second author was a Visiting Professor at the University of Arizona. Portions of this work were supported by the National Science Foundation under Grant MCS79-03428 and the National Science and Engineering Research Council under Grant A8237.
PY - 1980
Y1 - 1980
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85029614737&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85029614737&partnerID=8YFLogxK
U2 - 10.1109/SFCS.1980.4567820
DO - 10.1109/SFCS.1980.4567820
M3 - Conference article
AN - SCOPUS:85029614737
SN - 0272-5428
SP - 200
EP - 206
JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
M1 - 4567820
T2 - 21st Annual Symposium on Foundations of Computer Science, FOCS 1980
Y2 - 13 October 1980 through 15 October 1980
ER -