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, 9780818606441
DOIs
StatePublished - 1985
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

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