EFFICIENT PARTITION TREES

We prove a theorem on partitioning point sets in E(d) (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space, O(n log n) deterministic preprocessing time, and O(n1-1/d(log n)O(1)) query time. With O(n1 + delta)) preprocessing time, where delta is an arbitrary positive constant, a more complicated data structure yields query time O(n1-1/d(log log n)O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelle et al. [CSW]. The partition result implies that, for r(d) < n1 - delta, a (1/r)-approximation of size O(r(d)) with respect to simplices for an n-point set in E(d) can be computed in O(n log r) deterministic time. A (1/r)-cutting of size O(r(d)) for a collection of n hyperplanes in E(d) can be computed in O(n log r) deterministic time, provided that r less-than-or-equal-to n1/(2d - 1).