A data structure for efficiently answering such aggregate range queries can be based on the dominance ordering of the point set. A point x is said to dominate point y if y lies both below and to the left of x . The number of points m in the orthogonal rectangle defined by and is given by The second additive term corrects for the points for the lower left-hand corner that have been subtracted away twice. To answer arbitrary dominance queries efficiently, partition the space into rectangles by drawing a horizontal and vertical line through each of the n points. The set of points dominated is identical for each point in each rectangle, so the dominance count of the lower left-hand corner of each rectangle can precomputed, stored, and reported for any query point within it.
Queries reduce to binary search and thus take time.
Unfortunately, this data structure takes quadratic space. For each of these, Ranger supports queries in up to 25 dimensions under any Minkowski metric. See Section for details on both of them. The problem becomes considerably more difficult for nonorthogonal range queries, where the query region is not an axis-aligned rectangle.