A Succinct Data Structure for Multidimensional Orthogonal Range Searching
Kazuki Ishiyama, Kunihiko Sadakane · 2017
We introduce succinct representations of a d-dimensional point set supporting orthogonal range searching under two circumstances. First, we discuss this problem under the assumption that each coordinate of points takes a real number and we cannot change its encoding. In this case, it is usual to convert the point set into rank space. In this paper, we present a data structure using dn lg n + o(n lg n) bits, where n denotes the number of points in P, and supporting reporting queries in O((n(d-2)/d+ occ) lgn/lglgn) time, and counting queries in O(n(d-2)/dlg n/ lg lg n) time, where occ denotes the number of point to report. Secondly, we consider orthogonal range searching under the condition that each coordinate takes an integer in [U]1and we can change its encoding. In this case, we propose a succinct representation of the point set which requires dn lg U + o(n lg n) bits while supporting these queries in the same time complexity as that in rank space.