Reporting points in halfspaces

J Matousek - Computational Geometry, 1992 - Elsevier
J Matousek
Computational Geometry, 1992Elsevier
We consider the halfspace itrange itreporting problem: given a finite set P of points in R d,
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 (n 1− 1⌊ d 2⌋(logn) c+ k) query time, where …
We consider the halfspace itrange itreporting problem: given a finite set P of points in R d, 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 (n 1− 1⌊ d 2⌋(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 (n 1− 1⌊ d 2⌋ 2 c'log∗ n) with a linear space and O (n 1+ δ) preprocessing (c'= c'(d) is a constant and γ> 0 is arbitrarily small but fixed).
Elsevier