0
$\begingroup$

Given a set of 2 - D points (with integer x and integer y coordinates) and a set of queries containing the coordinates of a rectangle(integers).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This is called the 2-d orthogonal range counting problem.

Since you mentioned no constraints on the space usage, this can be done with $O(\log\log n)$ query time and $O(n^2)$ space in the RAM model using the predecessor algorithm.

The best small space solution in the RAM model requires $O(\log n/\log\log n)$ query time while taking $O(n\log^2 n)$ space. See the survey by Agarwal and Erickson.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .