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 -