Algorithms for three-dimensional dominance searching in linear space

摘要: Abstract We present several data structures for the following 3-dimensional dominance searching problem: store a set S of n points in R 3 structure, such that dominating query point q can be reported efficiently. All our use linear space. The first structure works restricted case where coordinates and are integers range [0, U − 1]. For this we achieve time O((log log U)2 + k U), is number answers to query. second third both work unrestricted case, arbitrary reals. O(log k) pointer machines random access (RAMs).