# assign points to non-overlapping rectangles

I have N (~100M) points in 2D and M (~10k) non-overlapping axis-parallel rectangles. I'm looking for an algorithm to assign each point to a rectangle it is contained in (or say that it is outside of any rectangle). I'm looking for a solution that works faster than bruteforce.

In 1D, it is achievable in N * log(M) using binary search. is something like that possible in 2D?

I care about practical performance. Two or more points can and often would be in the same rectangle, but the opposite never happens as rectangles are non-overlapping.

• Do you have any requirements on the assignment, like that no two points can be in the same rectangle? Or can you assign each point independently to any rectangle it is contained in? Do you care more about practical performance or theoretical worst-case asymptotic running time? – D.W. Jun 4 at 0:07
• Are your rectangles all axis-parallel, or can they be rotated? In the former case, orthogonal range searching is probably the best approach, but in the latter something like point location might be nessecary. In any case, you will likely need to construct some data structure on top of either the points or the rectangles. Is your data static, or is it dynamic? (i.e. do the points or rectangles change often in your application?) – Discrete lizard Jun 4 at 5:59
• (Searching sounds appropriate for query problems. I read the question to describe a *set problem.) Is bruteforce checking every (point, rectangle) pair, or do you consider a line sweep using brute force for the representation of current rectangles and search therein bruteforce, too? – greybeard Jun 4 at 7:15
• Replying to the comments: I care about practical performance. Two or more points can and often would be in the same rectangle. Rectangles are axis-parallel. Data is static. Line sweep would not be considered bruteforce, and it does sound interesting. – Maxim Imakaev Jun 4 at 11:41
• Please edit the question to incorporate all relevant information in the post itself, so people don't have to read the comments to understand what you're asking, and so that the question reads well for someone who encounters it for the first time. – D.W. Jun 5 at 2:07

Spatial indexes typically have about $$O(log{M})$$ insertion time so you could build in index in $$O(M * log{M})$$. Lookup time is similar, so finding the best/correct rectangle for every point should be around $$O(N * log{M})$$.
For rectangles, the simplest index is probably a quadtree (but may not scale as well with larger $$M$$). R-Trees such as the R*Tree (R-Star-Tree) are harder to implement but probably better than plain quadtrees. You could also look into STR-Trees (sort-tile-recurse-loaded R-Trees), they take longer to build but have faster lookup.