Halfspace range search
Bernard Chazelle, Franco P. Preparata · 1985
Given a fixed set S of n points in E3 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 Ο(n(log n)3(log log n)4) storage it is possible to solve this problem in Ο(κ + log n) time, where κ is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the maximum number of κ-sets realized by a set of n points in E3 is Ogr;(nkc) for a small positive constant c; a κ-set is any subset of S of size κ which can be separated from the rest of S by a plane. Incidentally, this result constitutes the only nontrivial upper bound, as a function of n and κ, known to date.