FRACTIONAL CASCADING: II. APPLICATIONS.

Bernard Chazelle; Leonidas J. Guibas

FRACTIONAL CASCADING: II. APPLICATIONS.

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

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 language	English (US)
Pages (from-to)	163-191
Number of pages	29
Journal	Algorithmica (New York)
Volume	1
Issue number	2
State	Published - 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
Computer Science Applications
Applied Mathematics

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 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.",

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

year = "1986",

language = "English (US)",

volume = "1",

pages = "163--191",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "2",

}

TY - JOUR

T1 - FRACTIONAL CASCADING

T2 - II. APPLICATIONS.

AU - Chazelle, Bernard

AU - Guibas, Leonidas J.

PY - 1986

Y1 - 1986

N2 - 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.

AB - 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.

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

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

M3 - Article

AN - SCOPUS:0023010035

SN - 0178-4617

VL - 1

SP - 163

EP - 191

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 2

ER -

FRACTIONAL CASCADING: II. APPLICATIONS.

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this