Fractional cascading: II. Applications

Bernard Chazelle; Leonidas J. Guibas

doi:10.1007/BF01840441

Fractional cascading: II. Applications

Bernard Chazelle, Leonidas J. Guibas

Research output: Contribution to journal › Article › peer-review

68 Scopus citations

Abstract

This paper presents several applications of fractional cascading, a new searching technique which has been described in a companion paper. 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 language	English (US)
Pages (from-to)	163-191
Number of pages	29
Journal	Algorithmica
Volume	1
Issue number	1
DOIs	https://doi.org/10.1007/BF01840441
State	Published - Mar 1 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

Computer Science(all)
Computer Science Applications
Applied Mathematics

Access to Document

10.1007/BF01840441

Cite this

@article{b54e49d5524243858eddf6559392d3c1,

title = "Fractional cascading: II. Applications",

abstract = "This paper presents several applications of fractional cascading, a new searching technique which has been described in a companion paper. 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.",

author = "Bernard Chazelle and Guibas, {Leonidas J.}",

year = "1986",

month = mar,

day = "1",

doi = "10.1007/BF01840441",

language = "English (US)",

volume = "1",

pages = "163--191",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Fractional cascading

T2 - II. Applications

AU - Chazelle, Bernard

AU - Guibas, Leonidas J.

PY - 1986/3/1

Y1 - 1986/3/1

N2 - This paper presents several applications of fractional cascading, a new searching technique which has been described in a companion paper. 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.

AB - This paper presents several applications of fractional cascading, a new searching technique which has been described in a companion paper. 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.

UR - http://www.scopus.com/inward/record.url?scp=0023010035&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023010035&partnerID=8YFLogxK

U2 - 10.1007/BF01840441

DO - 10.1007/BF01840441

M3 - Article

AN - SCOPUS:0023010035

SN - 0178-4617

VL - 1

SP - 163

EP - 191

JO - Algorithmica

JF - Algorithmica

IS - 1

ER -

Fractional cascading: II. Applications

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this