### Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 12th Colloquium |

Editors | Wilfried Brauer |

Publisher | Springer Verlag |

Pages | 90-100 |

Number of pages | 11 |

ISBN (Print) | 9783540156505 |

DOIs | |

State | Published - Jan 1 1985 |

Externally published | Yes |

Event | 12th International Colloquium on Automata, Languages and Programming, ALP 1985 - Nafplion, Greece Duration: Jul 15 1985 → Jul 19 1985 |

### Publication series

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

Volume | 194 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

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

Country | Greece |

City | Nafplion |

Period | 7/15/85 → 7/19/85 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Fractional cascading: A data structuring technique with geometric applications'. Together they form a unique fingerprint.

## Cite this

*Automata, Languages and Programming - 12th Colloquium*(pp. 90-100). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 194 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0015734