A 3-space partition and its applications
Fei Yao · 1983
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 a n points where a is a constant 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)