I have $N$ uniformly distributed 2D points and I want to find out how many points lie in some small rectangular region. However, the number of points can be arbitrarily large (e.g., $N=10^8$), so I don't want to explicitly generate points and insert them in some spatial data structure. I am not interested in the actual locations of points, just the number of them in some region. The search region is not known in advance, and I can perform queries in many different regions.

One solution is to use a quadtree and for every region query you traverse the tree and generate the number of points inside a node using multinomial distribution with probabilities 1/4 each.

For example, at the top level of the tree (level 1), there are N points. After one subdivision, nodes have $N_1$, $N_2$, $N_3$ and $N_4$ points that were distributed with multinomial distribution. The number of points in four children nodes must sum to the number of points in the parent node: $N = N_1 + N_2 + N_3 + N_4$. We continue traversal to some arbitrary depth level until we account for all quadtree nodes that overlapped the query region. This approach works, but the performance bottleneck is repeated generation of the number of particles in each node being traversed.

Question: Is there a way to compute the number of points in a region using purely probabilistic approach?

If there is a consistent enumeration of nodes in a quadtree, is there an algorithm that allows me to make a query "how many points lie in a quadtree node X at level L?" without explicit generation of the tree or hierarchical traversal described above?

  • $\begingroup$ Do you know the region in advance? You say you don't want to generate the points one-by-one and then count how many are in the region, but you don't say why not. Rather than saying "I don't want solution X", please try to identify some requirement that solution X violates. Is it you want running time to be better than $\Theta(N)$? Something else? How are the points distributed? Uniformly distributed on a larger rectangle? $\endgroup$ – D.W. Jan 9 '16 at 20:46

Yes, there are efficient solutions. Compute the area of the small rectangular region, and divide by the area of the entire region where the points are uniformly distributed. That is the probability that a single point falls within the small region; call this probability $p$. Now $pN$ (the product of $p$ and $N$) is the expected number of points within the small region.

More precisely, the number of points within the small region follows a Binomial$(N,p)$ distribution, so you can simulate a draw from that distribution with standard techniques. For instance, you can use the normal approximation (or, in some cases, the Poisson approximation) to very efficiently simulate drawing from this distribution.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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