Efficient uses of the past

David P. Dobkin; J. Ian Munro

doi:10.1016/0196-6774(85)90027-6

Efficient uses of the past

David P. Dobkin, J. Ian Munro

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

Existing data structures for maintaining sets do not remember the situation they represented 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 several important problems in geometric computation are also given.

Original language	English (US)
Pages (from-to)	455-465
Number of pages	11
Journal	Journal of Algorithms
Volume	6
Issue number	4
DOIs	https://doi.org/10.1016/0196-6774(85)90027-6
State	Published - Dec 1985

All Science Journal Classification (ASJC) codes

Control and Optimization
Computational Mathematics
Computational Theory and Mathematics

Access to Document

10.1016/0196-6774(85)90027-6

Cite this

@article{4c14c18e7f554876b3fadeb7ef0aca22,

title = "Efficient uses of the past",

abstract = "Existing data structures for maintaining sets do not remember the situation they represented 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 several important problems in geometric computation are also given.",

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

note = "Funding Information: *An earlier version of this paper appeared at the Twenty-First FOCS Conference, Syracuse, N.Y., October 1980. Portions of this work were supported by the National Science Foundation under Grants MCS81-14207 and MCS83-03926 and the National Science and Engineering Research Council under Grant A8237. Copyright: Copyright 2014 Elsevier B.V., All rights reserved.",

year = "1985",

month = dec,

doi = "10.1016/0196-6774(85)90027-6",

language = "English (US)",

volume = "6",

pages = "455--465",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Academic Press Inc.",

number = "4",

}

TY - JOUR

T1 - Efficient uses of the past

AU - Dobkin, David P.

AU - Munro, J. Ian

N1 - Funding Information: *An earlier version of this paper appeared at the Twenty-First FOCS Conference, Syracuse, N.Y., October 1980. Portions of this work were supported by the National Science Foundation under Grants MCS81-14207 and MCS83-03926 and the National Science and Engineering Research Council under Grant A8237. Copyright: Copyright 2014 Elsevier B.V., All rights reserved.

PY - 1985/12

Y1 - 1985/12

N2 - Existing data structures for maintaining sets do not remember the situation they represented 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 several important problems in geometric computation are also given.

AB - Existing data structures for maintaining sets do not remember the situation they represented 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 several important problems in geometric computation are also given.

UR - http://www.scopus.com/inward/record.url?scp=0042710372&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042710372&partnerID=8YFLogxK

U2 - 10.1016/0196-6774(85)90027-6

DO - 10.1016/0196-6774(85)90027-6

M3 - Article

AN - SCOPUS:0042710372

SN - 0196-6774

VL - 6

SP - 455

EP - 465

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 4

ER -

Efficient uses of the past

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this