Slimming down search structures: A functional approach to algorithm design
- 1 January 1985
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We establish new upper bounds on the complexity of several "rectangle" problems. Our results include, for instance, optimal algorithms for range counting and rectangle searching in two dimensions. These involve linear space implementations of range trees and segment trees. The algorithms we give are simple and practical; they can be dynamized and taken into higher dimensions. Also of interest is the nonstandard approach which we follow to obtain these results: it involves transforming data structures on the basis of functional specifications.Keywords
This publication has 15 references indexed in Scilit:
- Adding range restriction capability to dynamic data structuresJournal of the ACM, 1985
- New Data Structures for Orthogonal Range QueriesSIAM Journal on Computing, 1985
- Computational Geometry—A SurveyIEEE Transactions on Computers, 1984
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- Filtering search: A new approach to query-answeringPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- An Optimal Worst Case Algorithm for Reporting Intersections of RectanglesIEEE Transactions on Computers, 1980
- A unifying look at data structuresCommunications of the ACM, 1980
- A class of algorithms which require nonlinear time to maintain disjoint setsJournal of Computer and System Sciences, 1979
- A data structure for orthogonal range queriesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- Abstract data types and the development of data structuresCommunications of the ACM, 1977