# Datastructure for a set of axis aligned rectangles that enables querying for point containment

I am trying to find a reasonable data structure for representing a partition of an (axis aligned) rectangular domain into a set of (axis aligned) rectangles.

I need to be able to look up for a given point which (unique) rectangle contains it.

So far I have taken a look at Quadtrees, and this seems reasonable to me - where I recursively subdivide the domain into patches.

People have also mentioned RTrees, but I do not see how these can help me in such single point queries.

Quadtrees sounds like a good choice.

How about the k-d tree of 2 dimension, which is also explained in a course note and at geeksforgeeks?

Each of the 2-dimensional versions of interval tree, range tree and segment tree may have a fair chance to solve the question efficiently.

I have used all above data structures to solve the same or similar or more complex queries. Depending on your situation, you may want to make some adjustment.

If the number of given points is much smaller than the number of possible points in the given rectangle domain, such as 22000 points in a $10^{18}$ by $10^{18}$ square, then some other choice might be even better. I once used a red-black tree, whose leaf nodes is another red-black tree and whose internal nodes of the same parent represent a partition of the contiguous rows represented by their parent into disjoint contiguous set of rows. The red-black tree at each leaf node stores the points in one particular row. In this way (and with a bit more technique), my final answer is able to run the fastest among all solution to the problem. Of course, my example may not be useful to your situation at all. Well, I hope that might encourage you to develop your own data structure that fits your situation more.