Reporting points in halfspaces

AbstractWe consider the halfspace itrange itreporting problem: given a finite set P of points in Rd, preprocess it so that given a query halfspace γ, the points of P ∩ γ can be reported efficiently. We show that with almost linear storage, this problem can be solved substantially more efficiently that the more general simplex range searching problem. We give a data structure for halfspace range reporting in dimensions d ⩾ 4 with O(n log log n) space, O(n log n) deterministic preprocessing time and O(n1 − 1⌊d2⌋(logn)c + k) query time, where c = c(d) is a constant and k = |P ∩ γ| (efficient solutions were known for d = 2, 3). For the halfspace emptiness problem, where we only want to know whether P ∩ γ = Ø, we can achieve query time O(n1 − 1⌊d2⌋2c'log∗n) with a linear space and O(n1 + δ) preprocessing (c' = c'(d) is a constant and γ > 0 is arbitrarily small but fixed)