Reporting points in halfspaces

The author considers the halfspace range reporting problem: Given a finite set P of points in E^d, preprocess it so that given a query halfspace γ, the points of p∩γ can be reported efficiently. It is shown that, with almost linear storage, this problem can be solved substantially more efficiently than the more general simplex range searching problem. A data structure for halfspace range reporting in dimensions d⩾4 is given. It uses O(n log log n ) space and O (n log n) deterministic preprocessing time. The query time is also given. Results for the halfspace emptiness problem, where one only wants to know whether P∩γ is empty, are also presented