A general approach to d-dimensional geometric queries
Andrew Chi-Chih Yao, Fei Yao · 1985
It is shown that any bounded region in Ed can be divided into 2d subregions of equal volume in such a way that no hyperplane in Ed can intersect all 2d of the subregions. This theorem provides the basis of a data structure scheme for organizing n points in d dimensions. Under this scheme, a broad class of geometric queries in d dimensions, including many common problems in range search and optimization, can be solved in linear storage space and sublinear time.