Efficient uses of the past

David P. Dobkin; J. Ian Munro

doi:10.1109/SFCS.1980.4567820

Efficient uses of the past

David P. Dobkin, J. Ian Munro

Research output: Contribution to journal › Conference article › peer-review

20 Scopus citations

Abstract

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.

Original language	English (US)
Article number	4567820
Pages (from-to)	200-206
Number of pages	7
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs	https://doi.org/10.1109/SFCS.1980.4567820
State	Published - 1980
Event	21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States Duration: Oct 13 1980 → Oct 15 1980

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/SFCS.1980.4567820

Cite this

@article{a0b4459b23b94ee680266cce9ebcc31e,

title = "Efficient uses of the past",

abstract = "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.",

author = "Dobkin, {David P.} and Munro, {J. Ian}",

note = "Publisher Copyright: {\textcopyright} 1980 IEEE Computer Society. All rights reserved.; 21st Annual Symposium on Foundations of Computer Science, FOCS 1980 ; Conference date: 13-10-1980 Through 15-10-1980",

year = "1980",

doi = "10.1109/SFCS.1980.4567820",

language = "English (US)",

pages = "200--206",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

}

TY - JOUR

T1 - Efficient uses of the past

AU - Dobkin, David P.

AU - Munro, J. Ian

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 -

Efficient uses of the past

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this