SLIMMING DOWN SEARCH STRUCTURES: A FUNCTIONAL APPROACH TO ALGORITHM DESIGN.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

New upper bounds on the complexity of several 'rectangle' problems are established. The 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. Thee algorithms are simple and practical; they can be dynamized and taken into higher dimensions. Also of interest is the nonstandard approach used to obtain these results: it involves transforming data structures on the basis of functional specifications.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages165-174
Number of pages10
ISBN (Print)0818606444
StatePublished - Dec 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'SLIMMING DOWN SEARCH STRUCTURES: A FUNCTIONAL APPROACH TO ALGORITHM DESIGN.'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B. (1985). SLIMMING DOWN SEARCH STRUCTURES: A FUNCTIONAL APPROACH TO ALGORITHM DESIGN. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 165-174). IEEE.