EFFICIENT POINT LOCATION IN A CONVEX SPATIAL CELL-COMPLEX

In this paper a new approach is proposed to point-location in a three- dimensional cell-complex P, which may be viewed as a nontrivial genera lization of a corresponding two-dimensional technique due to Sarnak an d Tarjan. Specifically, in a space-sweep of P, the intersections of th e sweep-plane with P occurring in a given slab, i.e., between two cons ecutive 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 dat a structure, dynamically updated each time a vertex is swept. Combinin g the persistence-addition technique of Driscoll, Sarnak, Sleator, and Tarjan [J. Comput. System. Sci., 38 (1989), pp. 86-124] with the rece ntly discovered dynamic structure for planar point-location in monoton e subdivisions. a method with query time O(log2 N) and space O(N log2 N) for point-location in a convex cell-complex with N facets is obtain ed.