Halfspace range search: An algorithmic application of k-sets (Q1077166)

Given a fixed set \(S_ n\) of n points in Euclidean space \(E^ 3\) and a query plane \(\pi\), the halfspace range search problem asks for the retrieval of all points of \(S_ n\) on a chosen side of \(\pi\). The authors prove as main results: (1) the total number of j-sets of \(S_ n\) \((=subsets\) of \(S_ n\) of size j which can be separated from the rest of \(S_ n\) by a plane), \(j=1,...,k\), is \(O(nk^ 5)\); (2) using O(n(log n)\({}^ 8(\log \log n)^ 4)\) storage it is possible to solve the above half space range search problem in \(O(k+\log n)\) time, where k is the number of points to be reported.