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 O(n(log n)8 (loglog n)4) storage it is possible to solve this problem in O(k+log n) time, where k is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number of j-sets (j=1, ..., k) realized by a set of n points in E3 is O(nk5); a k-set is any subset of S of size k which can be separated from the rest of S by a plane.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics