1
$\begingroup$

Suppose you're given a population of $n$ points $(x_i, y_i)$ in the unit square $[0, 1]^2$. For a given new sample $(x, y)$, you must find the number of points in the original population satisfying $x\leqslant x_i$ and $y\leqslant y_i$.

Question: Can you beat the trivial $O(n)$ complexity under the constraints:

  • memory: $O\big(n(\log n)^{O(1)}\big)$;
  • pre-processing complexity: $O\big(n(\log n)^{O(1)}\big)$?

Illustration of the problem:

enter image description here

The one-dimension analogue is easily solved by first sorting the population ($O(n\log n)$ pre-processing) and then deducing the count from the position of the query in the sorted population ($O(\log n)$). This is not trivially extensible to multiple dimensions since treating the two dimensions independently requires to intersect 2 sets of (worst case) $O(n)$ elements in the end, which is not better than trivial.

An idea would be to partition the population into subsets either totally ordered (for $(x_1, y_1)\preccurlyeq (x_2, y_2) \Longleftrightarrow x_1\leqslant x_2 \land y_1\leqslant y_2$) or "totally unordered" (i.e. when a $y$-flip makes it totally ordered). This would give at most $O(n_{\text{subsets}}\log(n))$. Maybe there's a theorem providing an upper bound on such partition scheme?

Thanks in advance!

Improve this question
$\endgroup$
6
  • $\begingroup$ k-d trees, quadtrees, hell even a Fenwick tree might work $\endgroup$
    – qwr
    Commented Oct 17 at 13:30
  • $\begingroup$ you can use 2d prefix sums too. one for each axis and then subtract the overlap I think $\endgroup$
    – qwr
    Commented Oct 17 at 13:50
  • $\begingroup$ (@qwr: I'd be interested in a prefix sum solution to the 2D problem.) $\endgroup$
    – greybeard
    Commented Oct 18 at 6:02
  • $\begingroup$ Hi there, I only notice your commens now. Thanks for you time. I did edit my post when I found a solution, but to be honest @qwr, I don't feel like your chatbot-like answer helps much. $\endgroup$
    – ego-thales
    Commented Oct 24 at 11:48
  • $\begingroup$ do you slander other people who give you suggestions? $\endgroup$
    – qwr
    Commented Oct 24 at 12:30

1 Answer 1

Reset to default
0
$\begingroup$

It turns out range trees help solve this problem in $O\big((\log n)²\big)$ quite simply. This problem is known as (orthogonal) range search. It is essentially a "recursively defined multi-level binary search tree".

Improve this answer
$\endgroup$

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.