FRACTIONAL CASCADING: II. APPLICATIONS.

Bernard Chazelle, Leonidas J. Guibas

Research output: Contribution to journalArticlepeer-review

70 Scopus citations

Abstract

This paper presents several applications of fractional cascading, a new searching technique which has been described in part I. The applications center around a variety of geometric query problems. Examples include intersecting a polygonal path with a line, slanted range search, orthogonal range search, computing locus functions, and others. Some results on the optimality of fractional cascading, and certain extensions of the technique for retrieving additional information are also included.

Original languageEnglish (US)
Pages (from-to)163-191
Number of pages29
JournalAlgorithmica (New York)
Volume1
Issue number2
StatePublished - 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'FRACTIONAL CASCADING: II. APPLICATIONS.'. Together they form a unique fingerprint.

Cite this