Fractional cascading: I. A data structuring technique

Bernard Chazelle, Leonidas J. Guibas

Research output: Contribution to journalArticlepeer-review

313 Scopus citations

Abstract

In computational geometry many search problems and range queries can be solved by performing an iterative search for the same key in separate ordered lists. In this paper we show that, if these ordered lists can be put in a one-to-one correspondence with the nodes of a graph of degree d so that the iterative search always proceeds along edges of that graph, then we can do much better than the obvious sequence of binary searches. Without expanding the storage by more than a constant factor, we can build a data-structure, called a fractional cascading structure, in which all original searches after the first can be carried out at only log d extra cost per search. Several results related to the dynamization of this structure are also presented. A companion paper gives numerous applications of this technique to geometric problems.

Original languageEnglish (US)
Pages (from-to)133-162
Number of pages30
JournalAlgorithmica
Volume1
Issue number1-4
DOIs
StatePublished - Nov 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • B-tree
  • Binary search
  • Dynamization of data structures
  • Iterative search
  • Multiple look-up
  • Range query

Fingerprint

Dive into the research topics of 'Fractional cascading: I. A data structuring technique'. Together they form a unique fingerprint.

Cite this