# Fast Fractional Cascading and Its Applications

 Title Fast Fractional Cascading and Its Applications Publication Type Reports Year of Publication 2003 Authors Shi Q, JaJa JF Date Published 2003/08/01/ Institution Instititue for Advanced Computer Studies, Univ of Maryland, College Park Keywords Technical Report Abstract Using the notions of Q-heaps and fusion trees developed by Fredman andWillard, we develop a faster version of the fractional cascading technique while maintaining the linear space structure. The new version enables sublogarithmic iterative search in the case when we have a search tree and the degree of each node is bounded by $O(\log^{\epsilon}n)$, for some constant $\epsilon >0$, where $n$ is the total size of all the lists stored in the tree. The fast fractional cascading technique is used in combination with other techniques to derive sublogarithmic time algorithms for the geometric retrieval problems: orthogonal segment intersection and rectangular point enclosure. The new algorithms use $O(n)$ space and achieve a query time of $O(\log n/\log\log n + f)$, where $f$ is the number of objects satisfying the query. All our algorithms assume the version of the RAM model used by Fredman and Willard. (UMIACS-TR-2003-71) URL http://drum.lib.umd.edu/handle/1903/1296