Efficient Point Location in a Convex Spatial Cell-Complex

Abstract

In this paper a new approach is proposed to point-location in a three-dimensional cell-complex $\mathcal{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 $\mathcal{P}$, the intersections of the sweep-plane with $\mathcal{P}$ occurring in a given slab, i.e., between two consecutive vertices, are topologically conformal planar subdivisions. If the sweep direction is viewed as time, the descriptions of the various slabs are distinct “versions” of a two-dimensional point-location data structure, dynamically updated each time a vertex is swept. Combining the persistence-addition technique of Driscoll, Sarnak, Sleator, and Tarjan [J. Comput. System. Sci., 38 (1989), pp. 86–124] with the recently discovered dynamic structure for planar point-location in monotone subdivisions, 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 N facets is obtained.