%0 Journal Article
%J SIAM Journal on Computing
%D 2005
%T Novel transformation techniques using q-heaps with applications to computational geometry
%A Shi,Q.
%A JaJa, Joseph F.
%X Using the notions of Q-heaps and fusion trees developed by Fredman and Willard,we develop general transformation techniques to reduce a number of computational geometry prob- lems to their special versions in partially ranked spaces. In particular, we develop a fast fractional cascading technique, which uses linear space and enables sublogarithmic iterative search on catalog trees in the case when the degree of each node is bounded by O(log∈ n), for some constant ϵ > 0, where n is the total size of all the lists stored in the tree. We apply the fast fractional cascading tech- nique in combination with the other techniques to derive the first linear-space sublogarithmic time algorithms for the two fundamental geometric retrieval problems: orthogonal segment intersection and rectangular point enclosure.
%B SIAM Journal on Computing
%V 34
%P 1474 - 1492
%8 2005///
%G eng
%N 6