RANGE SEARCHING WITH EFFICIENT HIERARCHICAL CUTTINGS

We present an improved space/query-time tradeoff for the general simplex range searching problem, matching known lower bounds up to small polylogarithmic factors. In particular, we construct a linear-space simplex range searching data structure with O(n1-1/d) query time, which is optimal for d = 2 and probably also for d > 2. Further, we show that multilevel range searching data structures can be built with only a polyloprithmic overhead in space and query time per level (the previous solutions require at least a small fixed power of n). We show that Hopcroft's problem (detecting an incidence among n lines and n points) can be solved in time n(4/3)2O(log*n). In all these algorithms we apply Chazelle's results on computing optimal cuttings.