Consider the following special case of orthogonal range searching:

Given a set $S$ of $n$ points in $d$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $(0,0,...0)$, report the total number of points inside the rectangle.

This is different in that all rectangles queried have a fixed corner. In this case, will we have a dynamic algorithm with a better runtime, or is the problem still as hard as general orthogonal range searching?


1 Answer 1


The count of any rectangle $C(U, L, D, R)$ can be obtained combining the counts of 4 fixed "upper-left" retangles:

$C(U, L, D, R) = C(0, 0, D, R) - C(0, 0, U, R) - C(U, 0, D, L) + C(0, 0, U, L)$,

noting $C(up, left, down, right)$ the count in the rectangle delimited by $(up, left, down, right)$.

Thus, you cannot expect more than a factor 4 runtime improvement.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.