Efficient Point Location in a Convex Spatial Cell-Complex

In this paper we propose a new approach to point location in a three-dimensional cell complex {\em P}, which may be viewed as a nontrivial generalization of a corresponding two-dimensional technique due to Sarnak and Tarjan. Specifically, in a space-sweep of {\em P}, the intersections of the sweep-plane with {\em P} occurring in a slab, i.e., between two consecutive vertices, are topologically conformal planar subdivisions. If we view the sweep direction as time, the descriptions of the various slabs are distinct ``versions'''' of a two-dimensional point location data structure, dynamically updated each time we sweep a vertex. Combining the persistence-addition techniques of Driscoll {\em et al.}. with our recently discovered dynamic structure for planar point location in monotone subdivisions, we obtain a method with query time $O( \log ^ 2 N)$ and space $O( N \log ^2 N)$ for point location in a convex cell complex with {\em N} facets.