Fractional cascading: A data structuring technique with geometric applications

Bernard Chazelle, Leonidas J. Guibas

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

11 Scopus citations

Abstract

We examine the problem of searching for a given item in several sets. Let U be a linearly ordered universe and C be a finite collection of subsets of U; given an arbitrary query (x, H) with x ε U and H⊆C, search for x in each set of H. This operation, termed iterative search, is the bottleneck of a large number of retrieval problems. To perform it efficiently, we introduce a new technique, called fractional cascading. We demonstrate its versatility by applying it to a number of different geometric problems. Among the major applications of fractional cascading, we find improved methods for answering range queries, searching in the past, computing functions on d-ranges, intersection searching, solving general extensions of classical retrieval problems, answering visibility questions in the context of ray-tracing, etc.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 12th Colloquium
EditorsWilfried Brauer
PublisherSpringer Verlag
Pages90-100
Number of pages11
ISBN (Print)9783540156505
DOIs
StatePublished - Jan 1 1985
Externally publishedYes
Event12th International Colloquium on Automata, Languages and Programming, ALP 1985 - Nafplion, Greece
Duration: Jul 15 1985Jul 19 1985

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume194 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Colloquium on Automata, Languages and Programming, ALP 1985
CountryGreece
CityNafplion
Period7/15/857/19/85

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Chazelle, B., & Guibas, L. J. (1985). Fractional cascading: A data structuring technique with geometric applications. In W. Brauer (Ed.), Automata, Languages and Programming - 12th Colloquium (pp. 90-100). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 194 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0015734