A 3-space partition and its applications

Let S be a set of n points in three-dimensional space. It is shown that one can always find three planes that divide S into eight open regions, of which no seven together contain more than α n points where α is a constant < 1. This result gives rise to a data structure, what we call an octant-tree, for representing any point set in 3-space. Efficient solutions to various data retrieval problems are readily available with this structure. For example, using octant-trees, one can answer in sublinear time T (n) @@@@O(n^0.98) 1) half-space queries: find all points of S that lie to one side of a plane P; 2) polytope queries: find all points that lie inside (outside) a polytope; and 3) circular queries in E²: given a planar set S, find all points that lie within (without) a circle of radius r and center c for any r and c. An octant-tree for n points occupies O(n) space and can be constructed with O(n⁴) preprocessing time.