Convexity Helps Iterated Search in 3D

Abstract

Inspired by the classical fractional cascading technique [13, 14], we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph G with bounded degree together with a set Hv of 3D hyperplanes associated with every vertex of v of G. The goal is to store the input such that given a query point q ∈ R3 and a connected subgraph H ⊂ G, we can decide if q is below or above the lower envelope of Hv for every v ∈ H. We show that using linear space, it is possible to answer queries in roughly O(log n +|H| √log n) time which improves trivial bound of O(|H| log n) obtained by using planar point location data structures. Our data structure can in fact answer more general queries (it combines with shallow cuttings) and it even works when H is given one vertex at a time. We show that this has a number of new applications and in particular, we give improved solutions to a set of natural data structure problems that up to our knowledge had not seen any improvements. We believe this is a very surprising result because obtaining similar results for the planar point location problem was known to be impossible [15].