@article {14992,
	title = {Novel transformation techniques using q-heaps with applications to computational geometry},
	journal = {SIAM Journal on Computing},
	volume = {34},
	year = {2005},
	month = {2005///},
	pages = {1474 - 1492},
	abstract = {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.
},
	author = {Shi,Q. and JaJa, Joseph F.}
}
