Karlsson, R. G. (1986). Point Location in Discrete Computational Geometry. Technical Report LiTH-IDA-R-86-26, Department of Computer and Information Science, Linköping University, Sweden. A preliminary version appeared in Proc. 6th Brazilian Congress on Computing, July 1986. (bibtex),
Abstract: Based on efficient point location on two-dimensional grids fast solutions to several important problems in computational geometry are presented. For orthogonal objects log-logarithmic worst case time algorithms for point location, inclusion queries, and intersection queries, all using moderate storage, are obtained. Finally, an efficient range query algorithm is presented.
CS Dept TR Overview