2-DIMENSIONAL AND 3-DIMENSIONAL POINT LOCATION IN RECTANGULAR SUBDIVISIONS

We apply van Emde Boas-type stratified trees to point location problem s in rectangular subdivisions in 2 and 3 dimensions. In a subdivision with n rectangles having integer coordinates from [0, U - 1], we locat e an integer query point in O((log log U)(d)) query time using O(n) sp ace when d less than or equal to 2 or O(n log log U) space when d = 3. Applications and extensions of this ''fixed universe'' approach inclu de spatial point location using logarithmic time and linear space in r ectilinear subdivisions having arbitrary coordinates, point location i n c-oriented polygons or fat triangles in the plane, point location in subdivisions of space into ''fat prisms,'' and vertical ray shooting among horizontal ''fat objects.'' Like other results on stratified tre es, our algorithms run on a RAM model and make use of perfect hashing. (C) 1995 Academic Press, Inc.