Efficient partition trees

We prove a theorem on partitioning point sets inE ^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 logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).