Halfspace range search: An algorithmic application of k-sets

Given a fixed set S of n points in E³ and a query plane π, the halfspace range search problem asks for the retrieval of all points of S on a chosen side of π. We prove that with O(n(log n)⁸ (loglog n)⁴) storage it is possible to solve this problem in O(k+log n) time, where k is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number of j-sets (j=1, ..., k) realized by a set of n points in E³ is O(nk⁵); a k-set is any subset of S of size k which can be separated from the rest of S by a plane.