TY - GEN

T1 - Fractional cascading

T2 - 12th International Colloquium on Automata, Languages and Programming, ALP 1985

AU - Chazelle, Bernard

AU - Guibas, Leonidas J.

N1 - Funding Information:
Authors' current address: B. Chazelle: Department of Computer Science, Box 1910, Brown University, Providence, RI 02912, USA. L. Guibas: Digital Equipment Corp. --Systems Res. Center, 130 Lytton Ave., Palo Alto, CA 94301, USA. The first author was supported in part by NSF grant MCS 83-03925.

PY - 1985

Y1 - 1985

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

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

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

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

U2 - 10.1007/BFb0015734

DO - 10.1007/BFb0015734

M3 - Conference contribution

AN - SCOPUS:82155198464

SN - 9783540156505

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 90

EP - 100

BT - Automata, Languages and Programming - 12th Colloquium

A2 - Brauer, Wilfried

PB - Springer Verlag

Y2 - 15 July 1985 through 19 July 1985

ER -